Sachverhalt:
A. Am 27. August 2012 stellte das Betreibungsamt Oberwinterthur X._ gestützt auf ein Betreibungsbegehren des Steueramts der Stadt A._ in der Betreibung Nr. zzzz den Zahlungsbefehl zu. Dagegen erhob der Betriebene Aufsichtsbeschwerde an das Bezirksgericht Winterthur. Er verlangte sinngemäss die Aufhebung der Betreibung, da diese illegal und missbräuchlich eingeleitet worden sei. Das Bezirksgericht Winterthur als untere kantonale Aufsichtsbehörde wies die Beschwerde am 5. Oktober 2012 ab. Auf Beschwerde von X._ hob das Obergericht des Kantons Zürich als obere kantonale Aufsichtsbehörde diesen Entscheid am 20. November 2012 auf und wies das Bezirksgericht Winterthur an, dem Beschwerdeführer vor erneuter Entscheidfällung die Stellungnahme des Betreibungsamtes Oberwinterthur vom 2. Oktober 2012 zur Kenntnis zu bringen. Der Beschwerdeführer nahm die ihm vom Bezirksgericht Winterthur zugestellte Stellungnahme am 1. Dezember 2012 in Empfang. Mit Beschluss vom 10. Dezember 2012 wies das Bezirksgericht Winterthur die Beschwerde erneut ab. Gleich entschied das Obergericht des Kantons Zürich mit Urteil vom 28. Januar 2013.
B. Gegen dieses Urteil erhebt X._ (Beschwerdeführer) mit Eingabe vom 11. Februar 2013 (Datum der Postaufgabe) Beschwerde und subsidiäre Verfassungsbeschwerde. Er verlangt die Aufhebung des vorinstanzlichen Urteils. Diesen Antrag ergänzt er durch eine Fülle von Anträgen, die zur Hauptsache Bezug auf die Begründung nehmen. Schliesslich verlangt der Beschwerdeführer unentgeltliche Rechtspflege.
Es wurden die vorinstanzlichen Akten, aber keine Vernehmlassungen eingeholt.

Erwägungen:
1. 1.1 Das angefochtene Urteil ist der Endentscheid einer letzten kantonalen Instanz (Art. 90 und Art. 75 Abs. 1 BGG) in einer SchKG-Sache (<ref-law>). Rechtzeitig eingereicht ist auf die Beschwerde in Zivilsachen losgelöst vom Streitwert einzutreten (Art. 74 Abs. 2 lit. c und 100 Abs. 2 lit. a BGG). Die subsidiäre Verfassungsbeschwerde (<ref-law>) entfällt.
1.2 Bei der Beschwerde in Zivilsachen handelt es sich um ein reformatorisches Rechtsmittel (<ref-law>). Der Beschwerdeführer kann sich daher nicht darauf beschränken, die Aufhebung des vorinstanzlichen Urteils zu verlangen. Zumindest aus der Beschwerdebegründung ergibt sich, dass der nicht anwaltlich vertretene Beschwerdeführer "diese Betreibung wieder annuliert" haben will (Beschwerde S. 6). Damit ist von einem rechtsgenüglichen Rechtsbegehren auszugehen (<ref-law>; vgl. auch <ref-ruling> E. 1.4 S. 414 f.).
1.3 Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>). Unter Vorbehalt von hier nicht gegebenen Ausnahmen (Art. 95 lit. c-e BGG) ist die Verletzung des kantonalen Rechts im Beschwerdeverfahren vor Bundesgericht kein Beschwerdegrund. Diesbezüglich kann lediglich gerügt werden, die Anwendung des kantonalen Rechts durch die Vorinstanz verletze das Bundesrecht im Sinne von <ref-law> - namentlich das Willkürverbot (<ref-law>) - oder das Völkerrecht im Sinne von <ref-law> (<ref-ruling> E. 2.3 S. 466; <ref-ruling> E. 1.2.1 S. 251 f.).
1.4 Für alle Vorbringen betreffend die Verletzung verfassungsmässiger Rechte gilt das Rügeprinzip (<ref-law>). Die rechtsuchende Partei muss präzise angeben, welches verfassungsmässige Recht durch den angefochtenen kantonalen Entscheid verletzt wurde, und im Einzelnen darlegen, worin die Verletzung besteht (<ref-ruling>, E. 3.2 S. 444). Das Bundesgericht prüft nur klar und detailliert erhobene und, soweit möglich, belegte Rügen; auf ungenügend begründete Rügen und rein appellatorische Kritik am angefochtenen Entscheid tritt es nicht ein (<ref-ruling> E. 2.2 S. 246; <ref-ruling> E. 3.1 S. 399 f.). Wer sich auf eine Verletzung des Willkürverbots (<ref-law>) berufen will, kann sich demzufolge nicht darauf beschränken, den vorinstanzlichen Entscheid als willkürlich zu bezeichnen. Vielmehr ist anhand der angefochtenen Subsumtion im Einzelnen darzutun, inwiefern das kantonale Gericht willkürlich entschieden haben soll und der Entscheid an einem qualifizierten und offensichtlichen Mangel leidet (<ref-ruling> E. 2.2 S. 246; <ref-ruling> E. 4b S. 11 f.). Dies ist nach der ständigen Praxis des Bundesgerichts der Fall, wenn der angefochtene Entscheid offensichtlich unhaltbar ist, mit der tatsächlichen Situation in klarem Widerspruch steht, eine Norm oder einen unumstrittenen Rechtsgrundsatz krass verletzt oder in stossender Weise dem Gerechtigkeitsgedanken zuwiderläuft. Das Bundesgericht hebt einen Entscheid jedoch nur dann als willkürlich auf, wenn er nicht bloss in der Begründung, sondern auch im Ergebnis unhaltbar ist; dass eine andere Lösung ebenfalls als vertretbar oder gar zutreffender erscheint, genügt nicht (<ref-ruling> E. 4.1 S. 133 mit Hinweisen).
Diese Grundsätze verkennt der Beschwerdeführer über weite Strecken, wenn er der Vorinstanz in ausufernden Ausführungen, letztlich aber pauschal eine Verletzung von "Art. 5, Art. 8, Art. 9, Art. 29ff BV" (Beschwerde S. 4) bzw. "Art. 5, Art. 8, Art. 9, Art. 29ff BV bzw. <ref-law>" (Beschwerde S. 18) bzw. "Art. 5, Art. 8, Art. 9, Art. 29ff BV, Art. 2, Art. 18 KV ZH" und "EMRK Art. 6, Art. 13, Art. 14" (Beschwerde S. 21) vorwirft.
2. Nach Empfang des Betreibungsbegehrens erlässt das Betreibungsamt den Zahlungsbefehl (<ref-law>). Weder überprüft das Betreibungsamt dabei, ob die in Betreibung gesetzte Forderung materiell besteht, noch ob der Schuldner in der Lage ist, den Gläubiger zu befriedigen (zur Charakteristik des Einleitungsverfahrens: <ref-ruling> E. 4.1 S. 120; <ref-ruling> E. 4.1.1 S. 141 f.; <ref-ruling> E. 2a S. 150, je mit Hinweisen). Ob die Forderung der Steuerbehörden materiell Bestand hat, ist im Rahmen des Veranlagungsverfahrens bzw. eines allfälligen Rechtsmittelverfahrens zu prüfen. Demgegenüber entscheidet sich bei der Pfändung, ob und in welchen Umfang Einkommen und Vermögenswerte des Beschwerdeführers für eine Verwertung zur Verfügung stehen. Die Vorwürfe, die der Beschwerdeführer gegenüber dem Betreibungsamt in diesem Zusammenhang erhebt, sind unbegründet und gehen an der Sache vorbei. Dies gilt namentlich auch für den Vorwurf, dass das Betreibungsamt einen Zahlungsbefehl für eine Zinsforderung mit einem "offensichtlichen Wucherzins" ausgestellt habe (Beschwerde S. 6). Ist der Beschwerdeführer der Meinung, dass für die Geltendmachung dieses Zinses keine rechtliche Grundlage besteht, kann er den Fortgang der Betreibung dadurch hemmen, dass er Rechtsvorschlag erhebt (<ref-law>).
3. 3.1 Der Beschwerdeführer beruft sich auf kantonales Recht, konkret auf Weisungen der Steuerverwaltung ("Bezug Steuern RR ZH W33/013 Ziff. 47 und Ziff. 53 sowie RR ZH W34/010 u.a. Ziff. 46"). Ihnen will er entnehmen, dass im Kanton Zürich für "Leute in Finanznot" ein Betreibungsverbot gelte. Wie es sich damit verhält, kann offen bleiben. Das SchKG regelt die Zwangsvollstreckung auch für öffentlich-rechtliche Geldforderungen abschliessend (vgl. <ref-ruling> E. 3 S. 2). Weisungen der Steuerverwaltung können daher zum Vorneherein nur die Steuerverwaltung, nicht aber das Betreibungsamt binden. Die vom Beschwerdeführer behauptete gegenteilige Lösung verstiesse gegen den Vorrang des Bundesrechts (<ref-law>). Dieser verbietet es den Kantonen, dem Betreibungsamt in Bezug auf die in Betreibung gesetzte Forderung Prüfungspflichten aufzuerlegen, die im Bundesrecht nicht vorgesehen sind. Davon aber wäre auszugehen, wenn sich das Betreibungsamt darum kümmern müsste, ob sich die Steuerbehörden an regierungsrätliche Weisungen halten, wenn sie eine Steuerforderung in Betreibung setzen.
3.2 Vorbehalten bleibt der Vorwurf des Rechtsmissbrauchs (<ref-law>). Dieser lässt sich grundsätzlich auch gegenüber einer Behörde erheben. Auf Nichtigkeit einer Betreibung wegen Rechtsmissbrauchs kann nur in Ausnahmefällen erkannt werden, nämlich wenn es offensichtlich ist, dass der Gläubiger mit der Betreibung Ziele verfolgt, die nicht das Geringste mit der Zwangsvollstreckung zu tun haben (<ref-ruling>8 E. 3 S. 20 f.). Dem vorliegenden Sachverhalt ist nichts zu entnehmen, was das Vorgehen der Zürcher Steuerbehörden als rechtsmissbräuchlich erscheinen lässt und die Nichtigkeit des Zahlungsbefehls begründen könnte.
4. Es trifft zu, dass sämtliche Betreibungen auf dem Betreibungsregisterauszug erscheinen, was für den Schuldner nachteilig sein kann, namentlich bei der Suche nach einer neuen Wohnung oder Arbeitsstelle. Um dieses Problem im Fall unbegründeter Forderungen zu lösen, ist der Gesetzgeber gefordert. Daran ändert auch der vom Beschwerdeführer angerufene Art. 13 EMRK nichts, wonach jede Person, die in ihren Rechten verletzt worden ist, das Recht hat, bei einer innerstaatlichen Instanz Beschwerde zu erheben. Der Beschwerdeführer begründet nicht, in welchem Recht er durch die Ausstellung eines Zahlungsbefehls tatsächlich verletzt worden ist. Inwiefern dies der Fall wäre, ist auch nicht ersichtlich. Die Beschwerde erweist sich mithin als unbegründet.
5. Bei diesem Ausgang des Verfahrens wird der Beschwerdeführer grundsätzlich kostenpflichtig (<ref-law>). Das Gesuch des nicht anwaltlich vertretenen Beschwerdeführers um unentgeltliche Rechtspflege und Verbeiständung wird wegen Aussichtslosigkeit der Beschwerde in der Sache abgewiesen. Aufgrund der besonderen Umstände wird auf die Erhebung von Gerichtskosten verzichtet.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Es werden keine Gerichtskosten erhoben.
3. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, II. Zivilkammer, als obere kantonale Aufsichtsbehörde über Schuldbetreibung und Konkurs, schriftlich mitgeteilt.
Lausanne, 16. April 2013
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Das präsidierende Mitglied: Escher
Der Gerichtsschreiber: V. Monn