Sachverhalt: A. X._ liess am 5. und 6. November 2007 seinen Sohn im Stadtspital Triemli Zürich ambulant behandeln. Am 7. Januar 2008 stellte ihm das Stadtspital Triemli eine Schlussbabrechnung in Höhe von Fr. 690.35 zu. Nachdem X._ die Rechnung trotz zweimaliger Mahnung nicht beglichen hatte, wurde er am 28. Mai 2008 ein erstes Mal betrieben. Auf Rechtsvorschlag vom 3. Juni 2008 hin verlangte das Stadtspital Triemli - nach mehr als einem Jahr - beim Gesundheits- und Umweltdepartement der Stadt Zürich definitive Rechtsöffnung. Diese wurde am 9. Juni 2009 zuerst gewährt, aufgrund einer Einsprache von X._ beim Stadtrat Zürich jedoch mit Verfügung vom 17. August 2009 wiedererwägungsweise gestützt auf Art. 88 Abs. 2 SchKG aufgehoben. B. Am 21. September 2009 betrieb das Triemlispital den Beschwerdeführer erneut, wogegen dieser gleichentags Rechtsvorschlag erhob. Mit Verfügung vom 6. November 2009 verpflichtete das Gesundheits- und Umweltdepartement der Stadt Zürich X._ zur Bezahlung des Rechnungsbetrages von Fr. 690.35 und hob den Rechtsvorschlag auf. Die dagegen erhobenen kantonalen Rechtsmittel an den Stadtrat und den Bezirksrat Zürich sowie an das Verwaltungsgericht des Kantons Zürich blieben erfolglos. C. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 26. April 2011 verlangt X._, das Urteil des Verwaltungsgerichts vom 3. März 2011, der Beschluss des Bezirksrates Zürich vom 16. Dezember 2010 sowie die Beseitung des Rechtsvorschlages im Betreibungsverfahren vom 21. September 2009 seien aufzuheben. Zudem sei ihm die unentgeltliche Prozessführung zu gewähren. Die Stadt Zürich beantragt die Abweisung der Beschwerde, eventuell die Rückweisung an die Vorinstanz. Der Bezirksrat Zürich liess sich nicht vernehmen. Das Verwaltungsgericht des Kantons Zürich schliesst auf Abweisung, soweit auf die Beschwerde einzutreten sei. D. Der Präsident der II. öffentlich-rechtlichen Abteilung des Bundesgerichts hat der Beschwerde mit Verfügung vom 6. Juni 2011 antragsgemäss die aufschiebende Wirkung zuerkannt. 