Sachverhalt: A. A.a X._ wurde am 10. Januar 2007 in einem Tram der Linie 10 der städtischen Verkehrsbetriebe Zürich (VBZ; nachfolgend: Verkehrsbetriebe) bei der Haltestelle Milchbuck kurz nach acht Uhr morgens kontrolliert. Da er lediglich einen erst ab neun Uhr gültigen Fahrausweis (Monats-Abonnement mit beschränkter zeitlicher Gültigkeit) bei sich trug, händigten ihm die Kontrolleure um 08.06 Uhr einen mit der Aufforderung zur Zahlung eines Taxzuschlags von Fr. 80.-- verbundenen Einzahlungsschein aus. Gleichentags um zehn Uhr kaufte X._ einen während eines Monats gültigen Netzpass des Zürcher Verkehrsverbundes (ZVV) für Fr. 219.--. A.b Am 27. März 2007 gewährten die Verkehrsbetriebe X._ eine Stundung des geschuldeten Taxzuschlages bis zum 31. Dezember 2007 und eine anschliessende Ratenzahlung. Nachdem die am 28. Januar 2008 fällige erste Rate von Fr. 20.-- bis zum 7. März 2008 nicht geleistet worden war, verfügte der Direktor der Verkehrsbetriebe, X._ werde zur Bezahlung von insgesamt Fr. 130.-- (für Taxzuschlag zuzüglich Bearbeitungsaufwand) verpflichtet. B. B.a Am 9. Juli 2008 wies der Stadtrat von Zürich eine dagegen gerichtete Einsprache von X._ ab und auferlegte diesem die Verfahrenskosten von Fr. 262.--. B.b Mit Entscheid vom 2. April 2009 wies der Bezirksrat Zürich einen dagegen gerichteten Rekurs ebenfalls ab und auferlegte X._ die Verfahrenskosten von Fr. 515.--. B.c Am 17. Juli 2009 wies der Einzelrichter am Verwaltungsgericht des Kantons Zürich eine dagegen erhobene Beschwerde ab, soweit er darauf eintrat, und sprach Gerichtskosten von Fr. 560.-- zu Lasten von X._. C. C.a Mit als "staatsrechtliche Beschwerde" bezeichneter Eingabe vom 16. Oktober 2009 an das Bundesgericht beantragt X._, den Entscheid des Verwaltungsgerichts aufzuheben; für das bundes-gerichtliche Verfahren sei ihm die unentgeltliche Prozessführung zu gewähren. C.b Die Stadt Zürich und das Verwaltungsgericht des Kantons Zürich schliessen auf Abweisung der Beschwerde, soweit darauf einzutreten sei. Der Bezirksrat Zürich hat auf eine Vernehmlassung verzichtet. Das Bundesamt für Verkehr stellt für das Eidgenössische Departement für Umwelt, Verkehr, Energie und Kommunikation (UVEK) Antrag auf Gutheissung der Beschwerde und Aufhebung des Entscheids des Verwaltungsgerichts.