Sachverhalt: A. Der Anästhesiepfleger X._ wird im laufenden Strafverfahren beschuldigt, sich zwischen Mai 2008 und August 2011 an mindestens 14 Patientinnen sexuell vergangen zu haben. Im Zeitpunkt des Urteils des Verwaltungsgerichts des Kantons Zürich vom 9. August 2012 befand sich X._ in Untersuchungshaft. B. Der Kantonsärztliche Dienst des Kantons Zürich verbot X._ mit Verfügung vom 9. Januar 2012 im Sinne einer vorsorglichen Massnahme per sofort und unter Androhung der Ungehorsamsstrafe nach Art. 292 StGB die Ausübung seiner beruflichen Tätigkeit als Pfleger von Patientinnen im Kanton Zürich. Das Berufsverbot wurde bis zu dem Zeitpunkt angeordnet, in dem nach Vorliegen eines rechtskräftigen Entscheids in der Strafsache über die allfällige Verhängung eines definitiven Berufsverbots rechtskräftig entschieden worden sein wird. Zusätzlich verfügte der Kantonsärztliche Dienst des Kantons Zürich, dass das ausgesprochene Verbot im Amtsblatt des Kantons Zürich veröffentlicht wird, wenn X._ seine berufliche Tätigkeit als Pfleger vor dem definitiven Entscheid über das Berufsverbot wieder aufnimmt. Die dagegen erhobenen kantonalen Rechtsmittel blieben erfolglos. C. Vor Bundesgericht beantragt X._, das Urteil des Verwaltungsgerichts des Kantons Zürich vom 9. August 2012 aufzuheben und durch folgende Anordnung zu ersetzen: "Der Beschwerdeführer wird unter Strafandrohung gemäss Art. 292 StGB verpflichtet, nach seiner Haftentlassung, mithin vor Antritt einer eventuellen, pflegerischen Tätigkeit im Kanton Zürich oder in anderen Kantonen der Gesundheitsdirektion des Kantons Zürich hiervon zwecks vorgängiger Genehmigung eine Meldung zu erstatten." Eventualiter sei die Sache an die Vorinstanz zurückzuweisen. Ferner sei dem Beschwerdeführer die unentgeltliche Rechtspflege zu gewähren. Der Kantonsärztliche Dienst des Kantons Zürich und die Gesundheitsdirektion des Kantons Zürich beantragen die Abweisung der Beschwerde und des Gesuchs um aufschiebende Wirkung. Darauf hat der Beschwerdeführer mit Eingabe vom 18. Oktober 2012 repliziert. D. Mit Verfügung vom 9. Oktober 2012 hat der Abteilungspräsident das Gesuch um aufschiebende Wirkung abgewiesen.