Sachverhalt:
A. Mit Schreiben vom 15. Juni 2012 verlangte X._ im Rahmen einer gegen ihn laufenden Lohnpfändung vom Betreibungsamt Basel-Stadt die Berücksichtigung von ihm erwachsenen Kosten für insgesamt zehn Ausgabenpositionen (total Fr. 1'819.95) bzw. eine entsprechende Erhöhung des Existenzminimums. Mit Verfügung vom 28. Juni 2012 bewilligte das Betreibungsamt den Ausgleich des Existenzminimums für vier Positionen im Umfang von Fr. 656.05 und wies das Begehren im Übrigen ab.
B. Dagegen erhob X._ am 5. Juli 2012 erfolglos Beschwerde an die untere Aufsichtsbehörde (Entscheid vom 25. September 2012).
C. Am 8. November 2012 reichte X._ Beschwerde beim Appellationsgericht des Kantons Basel-Stadt als oberer kantonaler Aufsichtsbehörde ein. Mit Entscheid vom 3. Dezember 2012 wies das Appellationsgericht die Beschwerde ab, soweit es darauf eintrat.
D. Am 19. Dezember 2012 hat X._ (Beschwerdeführer) Beschwerde an das Bundesgericht erhoben. Er beantragt sinngemäss, den Entscheid der oberen Aufsichtsbehörde aufzuheben und seiner "ursprünglichen Forderung" zu entsprechen.
Am 29. Dezember 2012 hat der Beschwerdeführer zudem um unentgeltliche Rechtspflege ersucht.
Das Bundesgericht hat die Akten beigezogen, aber keine Vernehmlassungen eingeholt.

Erwägungen:
1. 1.1 Die Beschwerde in Zivilsachen ist gegen den Entscheid der oberen Aufsichtsbehörde in Schuldbetreibungs- und Konkurssachen unabhängig vom Streitwert zulässig (Art. 72 Abs. 2 lit. a, Art. 74 Abs. 2 lit. c, Art. 75 BGG).
1.2 Mit der Beschwerde in Zivilsachen können Rechtsverletzungen gemäss Art. 95 f. BGG geltend gemacht werden. Das Bundesgericht wendet das Recht grundsätzlich von Amtes wegen an (<ref-law>; vgl. für Ausnahmen Abs. 2 dieser Norm) und prüft mit freier Kognition, ob der angefochtene Entscheid Recht verletzt. Es befasst sich aber nur mit formell ausreichend begründeten Rügen (<ref-law>; <ref-ruling> E. 1.1 S. 104 f.). In der Begründung ist in gedrängter Form darzulegen, inwiefern der angefochtene Akt Recht verletzt. Allgemein gehaltene Einwände, die ohne aufgezeigten oder erkennbaren Zusammenhang mit bestimmten Entscheidungsgründen vorgebracht werden, genügen nicht (<ref-ruling> E. 1.3 S. 584 mit Hinweisen).
1.3 Für das Bundesgericht ist der vorinstanzlich festgestellte Sachverhalt grundsätzlich verbindlich (<ref-law>). Seine Feststellung kann nur gerügt werden, wenn sie offensichtlich unrichtig - d.h. willkürlich (<ref-ruling> E. 1.5 S. 130 mit Hinweis) - ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht und die Behebung des Mangels für den Verfahrensausgang entscheidend sein kann (<ref-law>). Inwiefern diese Voraussetzungen erfüllt sein sollen, muss in der Beschwerde substantiiert begründet werden (<ref-ruling> E. 4.2 S. 234; <ref-ruling> E. 5.1 S. 356). Dabei ist zu beachten, dass bei der Rüge der offensichtlich unrichtigen Sachverhaltsfeststellung das strenge Rügeprinzip (<ref-law>) gilt und demnach anhand der Erwägungen des angefochtenen Entscheids klar und detailliert darzulegen ist, inwiefern die vorinstanzliche Sachverhaltsfeststellung willkürlich sein soll. Demzufolge genügt es nicht, einen von den tatsächlichen Feststellungen der Vorinstanz abweichenden Sachverhalt zu behaupten (<ref-ruling> E. 1.4.2 und 1.4.3 S. 254 f.). Auf solche rein appellatorische Kritik am Sachverhalt tritt das Bundesgericht nicht ein (BGE <ref-ruling> E. 5.1 S. 356 mit Hinweis).
2. Das Appellationsgericht ist auf die Beschwerde insofern nicht eingetreten, als der Beschwerdeführer mit Eingabe vom 28. November 2012 neue Anträge gestellt hatte. Vor Bundesgericht kommt der Beschwerdeführer darauf nicht zurück. Insbesondere ist sein Antrag, seiner ursprünglichen Forderung zu entsprechen, so zu verstehen, dass er die Erhöhung des Existenzminimums nur in dem Umfang verlangt, wie er dies gegenüber dem Betreibungsamt getan hatte.
3. Das Appellationsgericht hat - wie bereits die untere Aufsichtsbehörde - erkannt, dass bezüglich der sechs noch umstrittenen Ausgabenpositionen das Begehren um Anpassung des Existenzminimums zu spät gestellt worden sei.
Die untere Aufsichtsbehörde, auf deren Erwägungen sich das Appellationsgericht bezieht, hat dazu auf eine Bestimmung in den Weisungen der Aufsichtsbehörde über die Berechnung des Existenzminimums hingewiesen, wonach der Schuldner aufgrund bestimmter, während der Dauer der Lohnpfändung anfallender Auslagen eine Änderung derselben beantragen könne. Es könnten nur die während dieser Zeit anfallenden Auslagen berücksichtigt werden, wobei der Zeitpunkt der Rechnungsstellung massgeblich sei. Vorliegend habe es zwei sich überschneidende Lohnpfändungsperioden gegeben (Pfändungsgruppe xxxx vom 18. Januar 2011 bis 18. Januar 2012 und Pfändungsgruppe yyyy vom 16. Mai 2011 bis 16. Mai 2012). Die sechs umstrittenen Positionen seien alle in die erste Lohnpfändungsgruppe gefallen. Diese erste Lohnpfändung sei bereits am 23. Februar 2012 abgerechnet worden und am 14. März 2012 seien die Betreffnisse ausgerichtet und die Verlustscheine versandt worden, so dass die Frist zur Beschwerdeerhebung längst abgelaufen sei.
Das Appellationsgericht hat auf entsprechende Einwände des Beschwerdeführers hin ausgeführt, es finde keine Gesamtbetrachtung der zwei sich überschneidenden Lohnpfändungsperioden statt. Es stehe nicht im Belieben des Schuldners, wann er ausserordentliche Auslagen geltend machen wolle, denn damit hätte er es in der Hand zu bestimmen, welche der Gläubigergruppen eine Schmälerung des Pfändungserlöses hinnehmen müsse. Im Übrigen verbleibe dem Schuldner ohnehin nur das Notwendige für den Lebensunterhalt, so dass er in der Regel gar nicht in der Lage sei, ausserordentliche Auslagen aus seinen freien Mitteln zu bestreiten. Diesfalls müsse er sowieso in zeitlicher Nähe zur Ausgabe vom Betreibungsamt die Rückerstattung oder sogar eine Bevorschussung verlangen. Um die Verspätung in der Geltendmachung zu entschuldigen, könne sich der Beschwerdeführer auch nicht auf den Brand vom 23. September 2011 im Haus berufen, in dem sich seine Wohnung befunden habe. Einerseits datierten die meisten der umstrittenen Posten auf einen weit vor dem Brand gelegenen Zeitpunkt, andererseits habe der Beschwerdeführer fünf Tage nach dem Brand bereits wieder eine Rechnung bezahlen können und sei somit in der Lage gewesen, seine administrativen und finanziellen Angelegenheiten zu regeln. Schliesslich habe der Beschwerdeführer spätestens im Herbst 2011 gewusst, dass er ausserordentliche Auslagen geltend machen könne, denn er habe am 7. Oktober 2011 beim Betreibungsamt vorgesprochen und zur Abdeckung von Spesen, die nach dem Brand entstanden waren, einen Betrag erhalten. Es sei unverständlich, dass er nicht zugleich Auslagenersatz für Kleider (eine der von ihm nun geltend gemachten Positionen) verlangt habe, die er nach dem Brand kaufen musste. Wenn er deswegen erst am 9. Januar 2012 vorgesprochen habe, aber sein Ansinnen mündlich abgelehnt worden sei, so hätte er dagegen Beschwerde erheben können. Als Mitarbeiter der Behörde Z._ habe er zweifellos gewusst, dass er eine beschwerdefähige Verfügung verlangen könne. Jedenfalls spätestens beim Abschluss des Pfändungsverfahrens bezüglich der Pfändungsgruppe xxxx hätte er Beschwerde erheben müssen.
4. Mit diesen Erwägungen setzt sich der Beschwerdeführer nicht in genügender Weise auseinander (vgl. oben E. 1.2). Er hält daran fest, dass es auf die einzelnen Lohnpfändungsgruppen nicht ankomme, sondern einzig auf die Tatsache, dass sein Lohn während der ganzen fraglichen Zeit und bis heute gepfändet worden sei. Weshalb seine Ansicht nicht zutrifft, hat das Appellationsgericht eingehend dargelegt; eine inhaltliche Auseinandersetzung mit diesen Gründen fehlt in der Beschwerde. Stattdessen verlagert er die Diskussion auf eine andere Ebene, nämlich dahin, er sei nie darauf hingewiesen worden, dass Rückforderungen überhaupt möglich seien und unter welchen Bedingungen bezüglich der einzelnen Pfändungsperioden sie erfolgen könnten. Damit übergeht der Beschwerdeführer die vorinstanzliche und grundsätzlich verbindliche Tatsachenfeststellung, dass er spätestens seit Herbst 2011 um die Rückerstattungsmöglichkeit wusste. Dass die Vorinstanz diesen Sachverhalt willkürlich festgestellt hätte, macht er jedoch nicht geltend (vgl. oben E. 1.3).
Der Beschwerdeführer verweist ausserdem auf zahlreiche von ihm eingereichte Akten. Der blosse Verweis auf Ausführungen in anderen Rechtsschriften oder auf die Akten ist jedoch unzulässig; vielmehr muss die Begründung in der Beschwerde selber enthalten sein (<ref-ruling> E. 3.2 S. 258; <ref-ruling> E. 3.1 S. 400 mit Hinweisen).
Schliesslich ersucht der Beschwerdeführer um die Möglichkeit der Verbesserung seiner Beschwerde, falls sie den Anforderungen nicht genügen sollte. Erfüllt die Beschwerde - wie vorliegend - die Begründungsanforderungen nicht, liegt darin jedoch kein Grund, der eine Rückweisung zur Verbesserung erlauben würde (Art. 42 Abs. 5 und 6 e contrario; <ref-ruling> E. 2.4.2 S. 247). Vielmehr ist darauf nicht einzutreten.
5. Bei diesem Ausgang des Verfahrens trägt der Beschwerdeführer die Gerichtskosten (<ref-law>). Nach dem Gesagten erweist sich die Beschwerde von vornherein als aussichtslos, so dass das Gesuch um unentgeltliche Rechtspflege abzuweisen ist (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Auf die Beschwerde wird nicht eingetreten.
2. Die Gesuch des Beschwerdeführers um unentgeltliche Rechtspflege wird abgewiesen.
3. Die Gerichtskosten von Fr. 500.-- werden dem Beschwerdeführer auferlegt.
4. Dieses Urteil wird den Verfahrensbeteiligten und dem Appellationsgericht des Kantons Basel-Stadt als obere kantonale Aufsichtsbehörde über das Betreibungs- und Konkursamt schriftlich mitgeteilt.
Lausanne, 24. Januar 2013
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Das präsidierende Mitglied: Escher
Der Gerichtsschreiber: Zingg