Sachverhalt: A. Am 23. Oktober 2006 erhielt der damals in Zürich wohnhafte X._ für seinen Hund B._ - einen männlichen American Staffordshire Terrier, geboren 2003 - vom Veterinäramt des Kantons Zürich gestützt auf ein vom Bezirkstierarzt Horgen am 18. Oktober 2006 erstattetes Gutachten (Wesenstest) die Bewilligung zur Befreiung des Tieres vom Leinen- und Maulkorbzwang. Wenig später, am 10. November 2006, wurde er von der Staatsanwaltschaft des Kantons St. Gallen wegen einer Reihe von Delikten (die zum Teil auch mit dem Handel und der Einfuhr von Hunden im Zusammenhang standen) zu drei Monaten Gefängnis (bedingt) und zu einer Busse von Fr.1'100.- verurteilt. Am 12. Juni 2007 wurde der Hund B._ streunend in der Nähe einer Kinderkrippe von der Stadtpolizei Zürich aufgegriffen und vom kantonalen Veterinäramt gleichentags provisorisch beschlagnahmt. X._ befand sich zu diesem Zeitpunkt (von Ende April 2007 bis Ende Juni 2007) in Untersuchungshaft und hatte die Betreuung seines Hundes einem Bekannten überlassen. Gestützt auf das Verhalten des Tieres im Tierheim T._ (Anspringen einer Pflegerin, neurologische Auffälligkeiten) verfügte das kantonale Veterinäramt, nachdem sich X._ schriftlich ausführlich geäussert hatte, am 3. Juli 2007 die definitive Beschlagnahmung und Euthanasierung des Hundes, unter Entzug der aufschiebenden Wirkung. Am 13. Juli 2007 brach X._ in das Tierheim ein, nahm den Hund an sich und verbrachte ihn nach Italien. Am 24. Juli 2007 erhob er gegen die Euthanasierungsverfügung zudem Rekurs an die Gesundheitsdirektion des Kantons Zürich, den diese am 6. Dezember 2007 abwies. Das Verwaltungsgericht des Kantons Zürich bestätigte diesen Entscheid auf Beschwerde hin am 13. März 2008. B. X._ erhebt gegen das Urteil des Verwaltungsgerichts mit Eingabe vom 18. Mai 2008 Beschwerde in öffentlich-rechtlichen Angelegenheiten mit dem Antrag, das angefochtene Urteil aufzuheben. Mit Schreiben vom 2. Juni 2008 ersucht er zudem um Gewährung der unentgeltlichen Rechtspflege. C. Das Verwaltungsgericht des Kantons Zürich beantragt - unter Verzicht auf Gegenbemerkungen - Abweisung der Beschwerde, ebenso die Gesundheitsdirektion des Kantons Zürich. Das kantonale Veterinäramt stellt in seiner Stellungnahme den Antrag, die Beschwerde abzuweisen. 