Sachverhalt: A. X._ ist seit Juni 2008 Eigentümer und Halter des 2006 geborenen, 25 kg schweren männlichen Hundes "A._" der Rasse Malinois (kurzhaariger belgischer Schäferhund). Am 20. August 2009 ereignete sich ein erster Zwischenfall, bei dem der Hund einen Rentner verbellte, so dass sich dieser bedroht fühlte. Am 3. September 2009 biss "A._" ein knapp 8-jähriges Mädchen ins Gesäss, was zu Prellungen und einer Schürfung führte. Wegen dieser beiden Vorfälle sprach das Statthalteramt des Bezirks Hinwil am 6. Oktober 2009 eine Busse von Fr. 250.-- aus. In der Folge häuften sich Beanstandungen wegen mangelnder Beaufsichtigung des Hundes "A._"; zu Anzeigen kam es jedoch nicht. Auf Anordnung des Veterinäramts des Kantons Zürich (nachfolgend: Veterinäramt) wurde beim Hund "A._" am 18. November 2009 ein Wesenstest durchgeführt. Dieser ergab keine Hinweise auf gestört aggressives Verhalten, jedoch wurden mangelhafter Appell und mangelhafte Kontrolle über den Hund festgestellt. Nach Gewährung des rechtlichen Gehörs am 8. März 2010 ordnete das Veterinäramt am 14. April 2010 für den Hund "A._" ab sofort die Leinenpflicht im öffentlich zugänglichen Raum an und verpflichtete X._, den Gehorsam, insbesondere den Appell seines Hundes, mit Hilfe einer Fachperson zu verbessern und die Ergebnisse des Trainings zu belegen. Gemäss Schlussbericht vom 10. November 2010 wurden die Trainingseinheiten per 31. Oktober 2010 abgeschlossen. Am 17. November 2010 wurde das Veterinäramt darüber informiert, dass der Hund "A._" praktisch nie an der Leine geführt werde und Anfang November 2010 zwei Kindergartenschüler belästigt habe. Das Veterinäramt ermahnte X._ am 14. Februar 2011, den auferlegten Leinenzwang einzuhalten. Am 8. September 2011 schnappte "A._" nahe dem Kindergarten nach einem 5 Jahre alten Kind und biss es durch den Maschendrahtzaun in den Bauch, was zu einer Prellung führte. Das Statthalteramt des Bezirks Hinwil bestrafte X._ deswegen am 29. September 2011 mit einer Busse von Fr. 600.--. Am 23. September 2011 beschlagnahmte das Veterinäramt den Hund "A._" vorsorglich. Nach Gewährung des rechtlichen Gehörs am 3. Oktober 2011 ordnete es am 9. November 2011 die definitive Beschlagnahmung des Hundes an und auferlegte X._ ein teilweises Hundehalteverbot (Beschränkung auf Gesellschaftshunde bis 10 kg Körpergewicht). Einem allfälligen Rekurs wurde die aufschiebende Wirkung entzogen. B. Das Gesuch um Wiederherstellung der aufschiebenden Wirkung wies die Gesundheitsdirektion des Kantons Zürich (nachfolgend: Gesundheitsdirektion) am 9. Februar 2012 ab. In der Hauptsache wies sie den Rekurs am 10. April 2012 ab und entzog einer allfälligen Beschwerde die aufschiebende Wirkung. Das Verwaltungsgericht des Kantons Zürich (nachfolgend: Verwaltungsgericht) bestätigte den angefochtenen Entscheid mit Urteil vom 4. Oktober 2012. C. X._ erhebt am 3. Dezember 2012 Beschwerde in öffentlich-rechtlichen Angelegenheiten beim Bundesgericht mit den Anträgen, das angefochtene Urteil sei aufzuheben; statt dessen sei für "A._" im öffentlich zugänglichen Raum eine Maulkorb- und Leinenpflicht zu verfügen und X._ zu verpflichten, mit dem Hund "A._" bei einer Fachperson Trainings- und Erziehungskurse so lange zu besuchen, wie es die Fachperson für nötig erachte; diese Auflagen seien unter Strafandrohung und gleichzeitiger Androhung der definitiven Beschlagnahme des Hundes "A._" zu erlassen. Das Verwaltungsgericht beantragt die Abweisung der Beschwerde, soweit darauf einzutreten sei. Die Gesundheitsdirektion, das Veterinäramt und das Bundesamt für Veterinärwesen (BVET) beantragen ebenfalls die Abweisung der Beschwerde. 