Sachverhalt: A. X._ war Eigentümer eines Hirten- und Schutzhundes der "Tornjak"-Hunderasse, welche in Kroatien sowie in Bosnien und Herzegowina beheimatet ist. Im August 2007 weilte er in den Ferien. Während dieser Zeit kümmerte sich seine von ihm getrennt lebende Ehefrau Y._ um den Hund. Am 15. August 2007 führte sie diesen um 11.00 Uhr an der Leine aus. Dabei griff der Hund unvermittelt eine Velofahrerin an und biss diese in den Oberschenkel sowie in den rechten Oberarm; sie musste im Spital ärztlich behandelt werden. Die Ehefrau konnte den Hund in das Haus zurückbringen. Der Polizei gelang es - der Aggressivität und des Gewichts (60 kg) des Hundes wegen - erst nach mehreren Versuchen unter Beizug ihres Hundespezialisten, das Haus zu betreten und ihn in ein Tierheim zu bringen. Der beigezogene stellvertretende Kantonstierarzt ordnete dort die sofortige Einschläferung des Hundes an. B. Am 21. August 2007 verfügte das kantonale Amt für Lebensmittel und Tiergesundheit, "der Hund [...] von X._ [...] wird per 15. August 2007 entschädigungslos beschlagnahmt und unverzüglich euthanasiert (getötet)". Eine Beschwerde dagegen wies das Departement für Volkswirtschaft und Soziales des Kantons Graubünden ab. Das Verwaltungsgericht bestätigte dessen Entscheid. C. Mit Eingabe vom 9. März 2009 beantragt X._, das Urteil des Verwaltungsgerichts des Kantons Graubünden vom 20. Januar 2009 sowie die Verfügung des Amtes für Lebensmittel und Tiergesundheit und den Entscheid des Departementes für Volkswirtschaft und Soziales des Kantons Graubünden aufzuheben und festzustellen, dass der Hund zu Unrecht euthanasiert wurde. Zur Begründung führt er im Wesentlichen aus, dass hierfür keine gesetzliche Grundlage bestehe und das Verhältnismässigkeitsprinzip verletzt worden sei. Das Departement und das Verwaltungsgericht beantragen, die Beschwerde abzuweisen.