Sachverhalt:
A. Das Statthalteramt des Bezirks Bülach verurteilte X._ mit Strafbefehl vom 4. Oktober 2012 wegen Verletzung des Anwaltsmonopols zu einer Busse von Fr. 400.-- (§ 40 des Anwaltsgesetzes des Kantons Zürich vom 17. November 2003 [LS 251.1]). Dagegen erhob X._ Einsprache. In der Folge lud ihn das Statthalteramt am 19. November 2012 auf den 4. Dezember 2012 zu einer Einvernahme vor. X._ verpasste diesen Termin und ersuchte das Statthalteramt am 5. Dezember 2012 um 6:23 Uhr per Fax, einen neuen Termin anzusetzen. Gleichentags stellte das Statthalteramt fest, der Strafbefehl vom 4. Oktober 2012 sei wegen Rückzugs der Einsprache rechtskräftig geworden.
X._ erhob gegen die Verfügung des Statthalteramts vom 5. Dezember 2012 Beschwerde ans Obergericht des Kantons Zürich. Dieses hiess das Rechtsmittel mit Verfügung vom 7. Februar 2013 teilweise gut und hob die angefochtene Verfügung auf. Es wies die Sache zur neuen Beurteilung ans Statthalteramt zurück, damit dieses die Voraussetzungen der Wiederherstellung des versäumten Termins prüfe. Das Obergericht erhob keine Kosten und sprach keine Entschädigung zu.
B. Mit Beschwerde in Strafsachen und subsidiärer Verfassungsbeschwerde ans Bundesgericht vom 13. März 2013 beantragt X._ im Wesentlichen, die Verfügung des Obergerichts vom 7. Februar 2013 sei aufzuheben und die Sache sei zur neuen Beurteilung zurückzuweisen. Das Obergericht sei dabei anzuweisen, ihm eine seinen tatsächlichen Aufwendungen und Auslagen entsprechende Parteientschädigung zuzusprechen.
Das Obergericht hat auf eine Vernehmlassung verzichtet. Das Statthalteramt des Bezirks Bülach äussert sich nicht zur Beschwerde, beantragt indessen, seine eigene Verfügung vom 5. Dezember 2012 sei zu bestätigen. Der Beschwerdeführer hält in seiner Stellungnahme dazu an seinen Anträgen und Rechtsauffassungen fest.

Erwägungen:
1. 1.1 Beim angefochtenen Entscheid handelt es sich um einen kantonal letztinstanzlichen Zwischenentscheid in Strafsachen (Art. 78, 80 und 93 BGG). Für die subsidiäre Verfassungsbeschwerde bleibt wegen der grundsätzlichen Zulässigkeit der Beschwerde in Strafsachen kein Raum, weshalb darauf nicht einzutreten ist.
1.2 Der Beschwerdeführer beantragt die Durchführung einer mündlichen und öffentlichen Parteiverhandlung und Urteilsberatung.
Die Durchführung einer mündlichen Parteiverhandlung gemäss <ref-law> ist grundsätzlich dem Ermessen des Abteilungspräsidenten anheim gestellt. Ein Anspruch darauf kann sich ausnahmsweise aus <ref-law> und Art. 6 Ziff. 1 EMRK ergeben. Dies ist insbesondere dann der Fall, wenn das Bundesgericht als einzige Instanz entscheidet und Rechte im Sinne von Art. 6 Ziff. 1 EMRK betroffen sind (Urteile 2C_844/2009 vom 22. November 2010 E. 3.2.3, in: sic! 3/2011 S. 166; 4A_612/2009 vom 10. Februar 2010 E. 4.2; 4A_370/2008 vom 1. Dezember 2008 E. 2, in: sic! 3/2009 S. 167; je mit Hinweisen). Vorliegend ist kein derartiger Ausnahmefall gegeben. Eine Parteiverhandlung ist deshalb nicht durchzuführen.
Eine mündliche und öffentliche Urteilsberatung ist ebenfalls nicht durchzuführen. Das Bundesgericht entscheidet grundsätzlich auf dem Weg der Aktenzirkulation und nur ausnahmsweise in einer öffentlichen Sitzung; die Voraussetzungen dafür sind hier nicht gegeben (<ref-law>).
1.3 Weiter ist zu prüfen, ob die Beschwerde in Strafsachen die Voraussetzungen von <ref-law> erfüllt. Sofern sich diese nicht ohne Weiteres aus den Akten ergeben, obliegt es dem Beschwerdeführer darzulegen, inwiefern sie gegeben sind (<ref-ruling> E. 1.1 S. 328 f.; <ref-ruling> E. 2.3.1 und 2.4.2 S. 632 f.; je mit Hinweisen). Vorliegend fällt von vornherein ausschliesslich die Variante von <ref-law> in Betracht. Danach ist die Beschwerde gegen einen Zwischenentscheid zulässig, wenn dieser einen nicht wieder gutzumachenden Nachteil bewirken kann.
Als oberste rechtsprechende Behörde des Bundes soll sich das Bundesgericht in der Regel nur einmal mit der gleichen Streitsache befassen müssen. Nach ständiger Praxis zu <ref-law> ist ein Vor- oder Zwischenentscheid daher nur ausnahmsweise anfechtbar, sofern ein konkreter rechtlicher Nachteil droht, der auch durch einen (für die rechtsuchende Partei günstigen) Endentscheid nachträglich nicht mehr behoben werden könnte.
Der in einem Zwischenentscheid enthaltene Kosten- und Entschädigungspunkt kann grundsätzlich nur im Rahmen einer Beschwerde gegen den Hauptpunkt ans Bundesgericht weitergezogen werden (<ref-ruling> E. 1 S. 331 ff. mit Hinweisen). Der Beschwerdeführer ficht den vorinstanzlichen Entscheid im Hauptpunkt nicht an; seine Beschwerde richtet sich ausschliesslich gegen den Entschädigungspunkt. Der in einem Zwischenentscheid enthaltene Entscheid über Kosten- und Entschädigungsfolgen kann jedoch allein grundsätzlich keinen nicht wieder gutzumachenden Nachteil bewirken (<ref-ruling> E. 2.2 f. S. 95 f. mit Hinweisen). Dass es vorliegend anders wäre, ist nicht ersichtlich und wird vom Beschwerdeführer auch nicht geltend gemacht. Auf die Beschwerde ist deshalb nicht einzutreten. Der Beschwerdeführer wird seine Kritik nach Vorliegen des Endentscheids (und unabhängig von dessen Inhalt) mit Beschwerde ans Bundesgericht vortragen können (<ref-law>; <ref-ruling> E. 1.2.2 S. 333; siehe zum Ganzen auch: Urteil 1B_488/2012 vom 21. Januar 2013 E. 1.3).
2. Auf die Beschwerde in Strafsachen und die subsidiäre Verfassungsbeschwerde ist aus den genannten Gründen nicht einzutreten.
Der Beschwerdeführer stellt ein Gesuch um unentgeltliche Rechtspflege. Da sein Rechtsbegehren nach dem Gesagten aussichtslos ist, ist das Gesuch abzuweisen. Der Beschwerdeführer trägt damit die Gerichtskosten (<ref-law>) und hat keinen Anspruch auf eine Parteientschädigung (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Auf die Beschwerde in Strafsachen und die subsidiäre Verfassungsbeschwerde wird nicht eingetreten.
2. Das Gesuch um unentgeltliche Rechtspflege wird abgewiesen.
3. Die Gerichtskosten von Fr. 1'000.-- werden dem Beschwerdeführer auferlegt.
4. Es wird keine Parteientschädigung zugesprochen.
5. Dieses Urteil wird dem Beschwerdeführer, dem Statthalteramt des Bezirks Bülach und dem Obergericht des Kantons Zürich, III. Strafkammer, schriftlich mitgeteilt.
Lausanne, 8. Mai 2013
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Fonjallaz
Der Gerichtsschreiber: Dold