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.

Erwägungen:
1. 1.1 Beim angefochtenen Entscheid handelt es sich um einen letztinstanzlichen kantonalen Entscheid in einer Angelegenheit des öffentlichen Rechts, die unter keinen Ausschlussgrund gemäss Art. 83 BGG fällt und daher mit Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht weitergezogen werden kann (Art. 82 lit. a und Art. 86 Abs. 1 lit. d BGG).
1. 1.1 Beim angefochtenen Entscheid handelt es sich um einen letztinstanzlichen kantonalen Entscheid in einer Angelegenheit des öffentlichen Rechts, die unter keinen Ausschlussgrund gemäss Art. 83 BGG fällt und daher mit Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht weitergezogen werden kann (Art. 82 lit. a und Art. 86 Abs. 1 lit. d BGG).
1.2 1.2.1 Zur Beschwerde ist nur legitimiert, wer u.a. ein schutzwürdiges Interesse an der Beurteilung seiner Eingabe hat (Art. 89 Abs. 1 lit. c BGG). Dieses muss nicht nur bei der Beschwerdeeinreichung, sondern auch noch im Zeitpunkt der Urteilsfällung aktuell und praktisch sein (<ref-ruling> E. 4 S. 286 f.). Fällt das schutzwürdige Interesse im Laufe des Verfahrens dahin, wird die Sache als erledigt erklärt; fehlte es schon bei der Beschwerdeeinreichung, ist auf die Eingabe nicht einzutreten (<ref-ruling> E. 2 S. 7). Das Bundesgericht verzichtet ausnahmsweise auf das Erfordernis des aktuellen praktischen Interesses, wenn sich die aufgeworfenen Fragen unter gleichen oder ähnlichen Umständen jederzeit wieder stellen können, eine rechtzeitige Überprüfung im Einzelfall kaum je möglich wäre und die Beantwortung wegen deren grundsätzlicher Bedeutung im öffentlichen Interesse liegt (<ref-ruling> E. 1.1 S. 81; Urteil 1C_89/2007 vom 13. Juli 2007 E. 1.3).
1.2.2 Am 15. August 2007 biss der Hund des Beschwerdeführers eine Velofahrerin. Gleichentags wurde er ohne Erlass einer Verfügung durch den stellvertretenden Kantonstierarzt eingeschläfert. Es handelt sich dabei um einen Realakt im Sinne des unmittelbaren Vollzugs oder - aufgrund einer Typisierung nach dem Verhältnis zur Verfügung - um einen verfügungsvertretenden Realakt (dazu PIERRE TSCHANNEN UND ANDERE, Allgemeines Verwaltungsrecht, 3. Aufl. 2009, S. 358, 360; PIERRE TSCHANNEN, Systeme des Allgemeinen Verwaltungsrechts, 2008, Rz. 169). Das zuständige kantonale Amt erliess am 21. August 2007 eine Verfügung, worin das Vorgehen zur Euthanasierung des Hundes gerechtfertigt wurde. Das Amt und das Departement vertraten die Auffassung, dass eine Verfügung zu erlassen sei, um damit gegen den Realakt eine Rechtsschutzmöglichkeit zu schaffen, obwohl nach Art. 28 Abs. 4 des Gesetzes vom 31. August 2006 über die Verwaltungsrechtspflege (VRG; BR 370.100; für die verwaltungsgerichtliche Beschwerde siehe Art. 49 Abs. 3 VRG) der Realakt selbst Anfechtungsobjekt einer Beschwerde bilden kann. Diese nachträgliche, ohne Anlass des Beschwerdeführers erlassene Verfügung kommt einer Feststellungsverfügung gleich. Darin wird die Rechtmässigkeit des Realaktes festgestellt. Auch die Anfechtung einer solchen Verfügung verlangt ein oben umschriebenes Rechtsschutzinteresse (<ref-ruling> E. 1.2 S. 365 f.; vgl. auch BEATRICE WEBER-DÜRLER, in: Auer und andere [Hrsg.], Kommentar zum Bundesgesetz über das Verwaltungsverfahren [VwVG], 2008, Rz. 30 zu Art. 25a VwVG). Das Bundesgericht verzichtet hier ausnahmsweise auf dieses: Eine Euthanasierung eines Hundes als verfügungsvertretender Realakt kann nie rechtzeitig überprüft werden, weshalb es im öffentlichen Interesse liegt, zu prüfen, wann eine solche zulässig ist.
1.2.2 Am 15. August 2007 biss der Hund des Beschwerdeführers eine Velofahrerin. Gleichentags wurde er ohne Erlass einer Verfügung durch den stellvertretenden Kantonstierarzt eingeschläfert. Es handelt sich dabei um einen Realakt im Sinne des unmittelbaren Vollzugs oder - aufgrund einer Typisierung nach dem Verhältnis zur Verfügung - um einen verfügungsvertretenden Realakt (dazu PIERRE TSCHANNEN UND ANDERE, Allgemeines Verwaltungsrecht, 3. Aufl. 2009, S. 358, 360; PIERRE TSCHANNEN, Systeme des Allgemeinen Verwaltungsrechts, 2008, Rz. 169). Das zuständige kantonale Amt erliess am 21. August 2007 eine Verfügung, worin das Vorgehen zur Euthanasierung des Hundes gerechtfertigt wurde. Das Amt und das Departement vertraten die Auffassung, dass eine Verfügung zu erlassen sei, um damit gegen den Realakt eine Rechtsschutzmöglichkeit zu schaffen, obwohl nach Art. 28 Abs. 4 des Gesetzes vom 31. August 2006 über die Verwaltungsrechtspflege (VRG; BR 370.100; für die verwaltungsgerichtliche Beschwerde siehe Art. 49 Abs. 3 VRG) der Realakt selbst Anfechtungsobjekt einer Beschwerde bilden kann. Diese nachträgliche, ohne Anlass des Beschwerdeführers erlassene Verfügung kommt einer Feststellungsverfügung gleich. Darin wird die Rechtmässigkeit des Realaktes festgestellt. Auch die Anfechtung einer solchen Verfügung verlangt ein oben umschriebenes Rechtsschutzinteresse (<ref-ruling> E. 1.2 S. 365 f.; vgl. auch BEATRICE WEBER-DÜRLER, in: Auer und andere [Hrsg.], Kommentar zum Bundesgesetz über das Verwaltungsverfahren [VwVG], 2008, Rz. 30 zu Art. 25a VwVG). Das Bundesgericht verzichtet hier ausnahmsweise auf dieses: Eine Euthanasierung eines Hundes als verfügungsvertretender Realakt kann nie rechtzeitig überprüft werden, weshalb es im öffentlichen Interesse liegt, zu prüfen, wann eine solche zulässig ist.
1.3 1.3.1 Das Bundesgericht wendet das Recht von Amtes wegen an (Art. 106 Abs. 1 BGG), doch prüft es, unter Berücksichtigung der allgemeinen Rüge- und Begründungspflicht (Art. 42 Abs. 1 und 2 BGG), nur die geltend gemachten Vorbringen, falls allfällige weitere rechtliche Mängel nicht geradezu offensichtlich sind (<ref-ruling> E. 1.4.1 S. 254). Der Grundsatz der Rechtsanwendung von Amtes wegen gilt nicht, soweit eine Verletzung von Grundrechten sowie von kantonalem und interkantonalem Recht geltend gemacht wird (vgl. Art. 106 Abs. 2 BGG). In diesem Fall müssen die Beschwerdeführer in ihrer Eingabe präzise und in Auseinandersetzung mit den Ausführungen der Vorinstanz im Einzelnen darlegen, inwiefern der angefochtene Entscheid widerrechtlich sein soll ("qualifizierte Rügepflicht"; vgl. <ref-ruling> E. 1.4.2 S. 254; <ref-ruling> E. 1.4 S. 287). Das Bundesgericht legt seinem Urteil zudem den von der Vorinstanz festgestellten Sachverhalt zugrunde (Art. 105 Abs. 1 BGG), es sei denn, dieser sei offensichtlich unrichtig oder beruhe auf einer Rechtsverletzung im Sinne von Art. 95 BGG (Art. 105 Abs. 2 BGG).
1.3.2 Unzulässig ist der Antrag des Beschwerdeführers, nicht nur das Urteil vom 26. Januar 2009 des Verwaltungsgerichts des Kantons Graubünden, sondern auch die Verfügung des Amtes für Lebensmittelsicherheit und Tiergesundheit vom 21. August 2007 aufzuheben: Diese wurde durch den angefochtenen Entscheid ersetzt (Devolutiveffekt); sie gilt lediglich inhaltlich als mitangefochten (vgl. <ref-ruling> E. 1 S. 441; <ref-ruling> E. 1c S. 33; BGE 2C_899/2008 vom 18. Juni 2009 E. 1.3.2).
1.3.3 Der Beschwerdeführer beantragt, festzustellen, dass sein Hund zu Unrecht euthanasiert wurde. Feststellungsbegehren sind vor Bundesgericht nur dann zulässig, wenn das schutzwürdige Interesse nicht ebensogut mit einem rechtsgestaltenden Begehren gewahrt werden kann (<ref-ruling> E. 2c S. 303). Das kantonale Amt hat eine Woche nach der Euthanasierung des Hundes dem Wortlaut nach eine Gestaltungsverfügung erlassen. Dem Sinn nach handelte es sich allerdings um eine Feststellungsverfügung, wie auch das Departement in seinem Entscheid vom 27. August 2008 hervorhob. Darin wird die Rechtmässigkeit der Euthanasierung festgestellt. Unter diesen Umständen kann der Beschwerdeführer seine Interessen mit einem rechtsgestaltenden Begehren nicht mehr wahrnehmen. Das Feststellungsbegehren ist deshalb zulässig.
2.1 2.1.1 Das Verwaltungsgericht des Kantons Graubünden stützte seinen Entscheid, den Hund zu euthanasieren, auf das im damaligen Zeitpunkt geltende (vgl. <ref-ruling> E. 5e/aa S. 598) Tierschutzgesetz vom 9. März 1978 (aTSchG; AS 1981 562, 1991 2345, 1995 1469 Art. 59 Ziff. 1, 2003 4181, 4803 Anhang Ziff. 3, 2006 2197 Anhang Ziff. 45). Nach Art. 25 aTSchG könne die zuständige Behörde, wenn sie eine Vernachlässigung oder eine völlig unrichtige Haltung von Tieren feststelle, unverzüglich einschreiten und alle sich aufdrängenden Massnahmen anordnen. Auch wenn in historischer Sicht die Norm zum Schutz der Tiere aufgestellt worden sei, müsse sie heute "zeitgemäss" ausgelegt werden. Zu berücksichtigen seien dabei die in den letzten Jahren vermehrt registrierten Beissunfälle, teilweise mit tödlichem Ausgang. Der Bundesrat habe deshalb im Jahre 2006 Art. 34a und 34b der Tierschutzverordnung vom 27. Mai 1981 (aTSchV; AS 1981 572, 1986 1408, 1991 2349, 1997 1121, 1998 2303, 2001 1337 Anhang Ziff. 1 2063, 2006 1427, 5217 Anhang Ziff. 2, 2007 1847 Anhang 3 Ziff. 1) erlassen, welche insbesondere den Schutz der Öffentlichkeit vor aggressiven Hunden bezweckten. Danach hätten die kantonalen Amtsstellen aggressive Hunde zu kontrollieren. Bei überdurchschnittlichem Aggressionsverhalten seien die erforderlichen Massnahmen zu ergreifen, wozu auch die Tötung des Tieres gehöre. Die gesetzliche Grundlage für die Tötung des Tieres sei daher zweifellos gegeben.
2.1.2 Der Beschwerdeführer rügt, dass Art. 25 aTSchG und Art. 34a und 34b aTSchV keine gesetzliche Grundlage bilde, um den Hund zu euthanasieren. Der Zweck des Tierschutzgesetzes bestehe im Schutz der Tiere und nicht im Schutz der Öffentlichkeit vor Tieren. Die von der Vorinstanz gewählte zeitgemässe Auslegung und die daraus gefolgerten, anwendbaren Massnahmen würden zudem der Verfassung widersprechen. Die Bundesverfassung gebe dem Bund keine Kompetenzen, Regelungen zum Schutz der Menschen vor Tieren zu erlassen. Dies würde auch durch diverse Gutachten bestätigt. Zudem würde die Tötung eines Hundes einen schweren Eingriff in das Eigentum darstellen, weshalb eine formell gesetzliche Grundlage notwendig wäre. Eine solche liege vorliegendenfalls gerade nicht vor. Selbst wenn eine genügend bestimmte gesetzliche Grundlage vorhanden wäre, würde durch das Vorgehen des kantonalen Amtes das Verhältnismässigkeits-prinzip, insbesondere die Erforderlichkeit und die Verhältnismässigkeit im engeren Sinne, verletzt.
2.1.2 Der Beschwerdeführer rügt, dass Art. 25 aTSchG und Art. 34a und 34b aTSchV keine gesetzliche Grundlage bilde, um den Hund zu euthanasieren. Der Zweck des Tierschutzgesetzes bestehe im Schutz der Tiere und nicht im Schutz der Öffentlichkeit vor Tieren. Die von der Vorinstanz gewählte zeitgemässe Auslegung und die daraus gefolgerten, anwendbaren Massnahmen würden zudem der Verfassung widersprechen. Die Bundesverfassung gebe dem Bund keine Kompetenzen, Regelungen zum Schutz der Menschen vor Tieren zu erlassen. Dies würde auch durch diverse Gutachten bestätigt. Zudem würde die Tötung eines Hundes einen schweren Eingriff in das Eigentum darstellen, weshalb eine formell gesetzliche Grundlage notwendig wäre. Eine solche liege vorliegendenfalls gerade nicht vor. Selbst wenn eine genügend bestimmte gesetzliche Grundlage vorhanden wäre, würde durch das Vorgehen des kantonalen Amtes das Verhältnismässigkeits-prinzip, insbesondere die Erforderlichkeit und die Verhältnismässigkeit im engeren Sinne, verletzt.
2.2 2.2.1 Nach Art. 25 Abs. 1 aTSchG schreitet die Behörde unverzüglich ein, wenn feststeht, dass Tiere stark vernachlässigt oder völlig unrichtig gehalten werden. Sie kann die Tiere vorsorglich beschlagnahmen und sie auf Kosten des Halters an einem geeigneten Ort unterbringen; wenn nötig lässt sie die Tiere verkaufen oder töten. Sie kann dafür die Hilfe der Polizeiorgane in Anspruch nehmen. Die Analyse des Art. 25 aTSchG zeigt: Der Tatbestand des Art. 25 Abs. 1 Satz 1 aTSchG steckt den Geltungsbereich des gesamten Artikels ab. Nur wenn feststeht, dass Tiere stark vernachlässigt oder völlig unrichtig gehalten werden, kann die Behörde die in Art. 25 aTSchG vorgesehenen Massnahmen anordnen, nötigenfalls kann sie Tiere verkaufen und töten. Sind Tiere stark vernachlässigt oder völlig unrichtig gehalten, so sind ihnen Leiden, Schmerzen oder Schäden zugefügt worden oder ihr Wohlbefinden ist erheblich beeinträchtigt (vgl. Antoine F. Goetschel, Kommentar zum Eidgenössischen Tierschutzgesetz, 1986, S. 180). Art. 25 aTSchG bildet somit die notwendige Verwaltungsmassnahme (vgl. Sachüberschrift zum zehnten Abschnitt), um die in Art. 2 aTSchG festgehaltenen tierschutzrechtlichen Grundsätze (Sorge für das Wohlbefinden, Verbot der Zufügung von Schmerzen, Leiden oder Schäden) durchzusetzen. Art. 25 aTSchG will somit nicht Menschen vor Tieren, sondern vielmehr Tiere vor Menschen schützen. Eine Tötung des Tieres nach Art. 25 aTSchG ist deshalb nur dann zulässig, wenn dessen Schmerzen oder Leiden aufgrund einer Vernachlässigung oder unrichtigen Haltung nicht mit vernünftigen Mitteln auf andere Weise gelindert oder geheilt werden können.
Aus den Akten ergibt sich (Art. 105 Abs. 1 BGG), dass der Hund zum Schutz vor Menschen und nicht wegen Vernachlässigung oder unrichtiger Haltung euthanasiert worden ist. Art. 25 aTSchG kann deshalb keine Grundlage hierfür bilden. An diesem Ergebnis ändert auch eine geltungszeitliche Auslegung nichts, insbesondere dann nicht, wenn sie die verfassungsrechtliche Kompetenzordnung umstösst. Dem Bund steht nach dem geltenden Verfassungsrecht keine Kompetenz zu, Vorschriften zum Schutz des Menschen vor gefährlichen Hunden zu erlassen (<ref-ruling> E. 3.2 S. 254; <ref-ruling> E. 2 S. 174 ff.; vgl. Gutachten des Bundesamtes für Justiz vom 5. September 2000, VPB 65.1; Markus Müller/Reto Feller, Gesetzgebungskompetenz des Bundes zum Schutz des Menschen vor gefährlichen Tieren (insb. Hunden), VPB 2007.10; Parlamentarische Initiative, Verbot von Pitbulls in der Schweiz, Bericht vom 20. Februar 2009 der Kommission für Wissenschaft, Bildung und Kultur des Nationalrates, BBl 2009 3547, 3567 Ziff. 2.6.2). Auch eine geltungszeitliche Auslegung hat sich an der föderalen Kompetenzordnung zu orientieren. Würde im Übrigen die Argumentation des Verwaltungsgerichts des Kantons Graubünden zutreffen, so würden aufgrund von Art. 49 Abs. 1 BV alle kantonalen Regelungen (siehe dazu BBl 2009 3557 f. Ziff. 2.3) einschliesslich der Art. 64 ff. des Veterinärgesetzes des Kantons Graubünden vom 30. August 2007 (VetG; BR 914.000), die Massnahmen gegen gefährliche Hunde normieren, obsolet.
2.2.2 Das Verwaltungsgericht stützt sich zudem auf Art. 34a und Art. 34b aTSchV, welche auf den 2. Mai 2006 in Kraft gesetzt wurden (AS 2006 1427, 1429). Danach sind Verletzungen an Menschen oder Tieren durch Hunde sowie ein übermässiges Aggressionsverhalten der Hunde zu melden (Art. 34a TSchV). Nach Art. 34b aTSchV hat die zuständige kantonale Behörde nach Eingang einer solchen Meldung den Sachverhalt zu überprüfen (Abs. 1). Ergibt die Überprüfung, dass ein Hund Abnormitäten im Verhalten, insbesondere ein übermässiges Aggressionsverhalten zeigt, so ordnet die zuständige kantonale Stelle die erforderlichen Massnahmen an (Abs. 3 ). Nach Absatz 4 kann sie anordnen, dass der Hundehalter bestimmte Kurse über den Umgang mit Hunden besuchen muss.
Art. 34b Abs. 3 aTSchV spricht von erforderlichen Massnahmen. Zwar ist diese Regelung unbestimmt, doch wird unter Berücksichtigung der föderalen Kompetenzen und der gesetzlichen Grundlage, auf welche sich die beiden Bestimmungen stützen, eine Tötung eines aggressiven Hundes davon nicht erfasst: Die beiden Verordnungsbestimmungen stützen sich einerseits auf Art. 33 aTSchG, der den Bundesrat ermächtigt, die Vollzugsvorschriften im Sinne von Art. 182 Abs. 2 BV zu erlassen. Andererseits basieren sie auf dem vorzeitig (dazu Verordnung vom 12. April 2006 über die vorzeitige Inkraftsetzung von Artikel 6 Absatz 3 des Tierschutzgesetzes vom 16. Dezember 2005 [AS 2006 1423]) in Kraft gesetzten Art. 6 Abs. 3 des Tierschutzgesetzes vom 16. Dezember 2005 (TSchG; SR 455). Danach kann der Bundesrat Anforderungen an die Aus- und Weiterbildung der Tierhalterinnen und Tierhalter sowie der Personen, die Tiere ausbilden, festlegen. Die Massnahmen betreffen somit die Personen, die mit Tieren umgehen. Dies bestätigt auch die Verordnung selbst: In Art. 34b Abs. 4 aTSchV - also nach Erwähnung der erforderlichen Massnahmen in Abs. 3 - wird ausdrücklich hervorgehoben, dass die zuständige kantonale Behörde anordnen kann, dass der Hundehalter bestimmte Kurse über den Umgang mit Hunden besuchen muss. Wird also diese Massnahme als strengstmöglicher Eingriff besonders hervorgehoben, können die erforderlichen Massnahmen nach Abs. 3 jedenfalls eine Tötung von aggressiven Hunden nicht umfassen (siehe in diesem Sinne auch Müller/Feller, a.a.O., S. 206 zum neuen Tierschutzrecht, wobei Art. 34a und 34b aTSchV Art. 78 und 79 TSchV [SR 455.1] entsprechen).
Art. 34b Abs. 3 aTSchV spricht von erforderlichen Massnahmen. Zwar ist diese Regelung unbestimmt, doch wird unter Berücksichtigung der föderalen Kompetenzen und der gesetzlichen Grundlage, auf welche sich die beiden Bestimmungen stützen, eine Tötung eines aggressiven Hundes davon nicht erfasst: Die beiden Verordnungsbestimmungen stützen sich einerseits auf Art. 33 aTSchG, der den Bundesrat ermächtigt, die Vollzugsvorschriften im Sinne von Art. 182 Abs. 2 BV zu erlassen. Andererseits basieren sie auf dem vorzeitig (dazu Verordnung vom 12. April 2006 über die vorzeitige Inkraftsetzung von Artikel 6 Absatz 3 des Tierschutzgesetzes vom 16. Dezember 2005 [AS 2006 1423]) in Kraft gesetzten Art. 6 Abs. 3 des Tierschutzgesetzes vom 16. Dezember 2005 (TSchG; SR 455). Danach kann der Bundesrat Anforderungen an die Aus- und Weiterbildung der Tierhalterinnen und Tierhalter sowie der Personen, die Tiere ausbilden, festlegen. Die Massnahmen betreffen somit die Personen, die mit Tieren umgehen. Dies bestätigt auch die Verordnung selbst: In Art. 34b Abs. 4 aTSchV - also nach Erwähnung der erforderlichen Massnahmen in Abs. 3 - wird ausdrücklich hervorgehoben, dass die zuständige kantonale Behörde anordnen kann, dass der Hundehalter bestimmte Kurse über den Umgang mit Hunden besuchen muss. Wird also diese Massnahme als strengstmöglicher Eingriff besonders hervorgehoben, können die erforderlichen Massnahmen nach Abs. 3 jedenfalls eine Tötung von aggressiven Hunden nicht umfassen (siehe in diesem Sinne auch Müller/Feller, a.a.O., S. 206 zum neuen Tierschutzrecht, wobei Art. 34a und 34b aTSchV Art. 78 und 79 TSchV [SR 455.1] entsprechen).
2.3 Damit bilden die von der Vorinstanz dem Entscheid zugrunde gelegten bundesrechtlichen Vorschriften keine gesetzliche Grundlage für die Euthanasierung des Hundes des Beschwerdeführers. Es stellt sich deshalb die Frage, ob sich eine gesetzliche Grundlage aus dem kantonalen Recht ergibt.
2.3.1 Der Kanton Graubünden hat am 30. August 2007 ein neues Veterinärgesetz erlassen (VetG; BR 914.000). Art. 64 ff. regeln die Hundehaltung, einschliesslich der Voraussetzungen von Wesensprüfungen (Art. 65) und der Anordnung der notwendigen Massnahmen zur Sicherung gefährlicher Tiere (Art. 66). Die Regierung hat gestützt auf Art. 83 Abs. 2 VetG das Gesetz auf den 1. Dezember 2008 in Kraft gesetzt. Entsprechend dem Grundsatz, dass für die bundesgerichtliche Beurteilung - mangels einer auf den vorliegenden Sachverhalt anwendbaren gesetzlichen Übergangsregelung - grundsätzlich die Rechtslage massgebend ist, wie sie bestand, als der angefochtene Verwaltungsakt erging (<ref-ruling> E. 5e/aa S. 598 mit Hinweisen), und die behördliche Handlung im August 2007 erfolgte, sind die Vorschriften über die Hundehaltung des VetG vorliegend nicht anwendbar.
2.3.2
2.3.2.1 Das kantonale Departement für Volkswirtschaft und Soziales hat sich in seinem Entscheid vom 27. August 2008 ferner eventualiter auf die polizeiliche Generalklausel gestützt. Die polizeiliche Generalklausel kann nach Art. 36 Abs. 1 BV eine fehlende gesetzliche Grundlage ersetzen und - selbst schwerwiegende - Eingriffe in Grundrechte legitimieren, wenn und soweit die öffentliche Ordnung und fundamentale Rechtsgüter des Staates oder Privater gegen schwere und zeitlich unmittelbar drohende Gefahren zu schützen sind, die unter den konkreten Umständen nicht anders abgewendet werden können als mit gesetzlich nicht ausdrücklich vorgesehenen Mitteln; diese müssen allerdings mit den allgemeinen Prinzipien des Verfassungs- und Verwaltungsrechts, insbesondere dem Grundsatz der Verhältnismässigkeit, vereinbar sein (<ref-ruling> E. 4b S. 118; <ref-ruling> E. 4b/aa S. 27 f.; <ref-ruling> E. 2 und 3a mit Hinweisen). Das Bundesgericht verlangt zudem, dass der Anwendungsbereich der polizeilichen Generalklausel auf echte und unvorhersehbare Notfälle zu beschränken sei; ihre Anrufung sei grundsätzlich ausgeschlossen, wenn typische und erkennbare Gefährdungslagen trotz Kenntnis der Problematik nicht normiert wurden (<ref-ruling> E. 7.3 S. 381 ff.; <ref-ruling> E. 4b S. 118; <ref-ruling> E. 4b/aa S. 27 f.; dazu kritisch Markus Müller/ Christoph Jenni, Die polizeiliche Generalklausel. Ein Institut mit Reformbedarf, Sicherheit&Recht, 2008, S. 4 ff.; Pierre Tschannen und andere, a.a.O., S. 517, 519; Regina Kiener/ Walter Kälin, Grundrechte, 2007, S. 95 f.). Handelt es sich bei der Gefährdung um eine solche von Leib und Leben, somit um einen Fall "ernster, unmittelbarer und nicht anders abwendbarer Gefahr" (Art. 36 Abs. 1 Satz 3 BV), ist dieses zusätzliche Kriterium indes nicht sachgerecht (vgl. Kiener/Kälin, a.a.O., S. 95). Ein Untätigsein des Gesetzgebers darf - wie vorliegendenfalls - dem möglichen Opfer einer ernsthaften und konkreten Gefährdung durch private Gewalt nicht zum Nachteil gereichen, zumal in diesem Bereich staatliche Schutzpflichten bestehen (vgl. <ref-ruling> E. 2 S. 31; <ref-ruling> E. 5a und 5b S. 314 f.; im Ergebnis auch <ref-ruling> E. 5c S. 120 f.; Rainer J. Schweizer, Die Schweizerische Bundesverfassung, 2. Aufl. 2008, N 35 ff., insbes. N 35 zu Art. 10 BV; zu Beispielen vgl. Jörg Paul Müller/ Markus Schefer, Grundrechte in der Schweiz, 2009, S. 53 ff., 74 ff. m.w.H.).
2.3.2.2 Wie aus den Akten zu entnehmen ist, stellte der Hund des Beschwerdeführers nicht nur im Zeitpunkt, als er die Velofahrerin unmotiviert angegriffen und gebissen hatte, eine unmittelbare Gefahr für die Gesundheit und das Leben - unstreitig fundamentale Rechtsgüter - dar: So reagierte er besonders aggressiv und ohne Anlass bei dunkel gekleideten Personen, weshalb die Ehefrau den Hund auch an Randzeiten ausgeführt hatte; es bestand deshalb grundsätzlich eine potentiell dauerhafte Gefahrensituation. Zudem gefährdete er auch nach dem Angriff auf die Velofahrerin mit seiner Aggressivität die herbeigerufenen Polizisten, welche ihn nur in Schutzmontur bändigen und in ein Tierheim bringen konnten. Die Gefahrensituation dauerte somit auch nach dem Angriff auf die Velofahrerin an. Selbst im Tierheim traf diese Konstellation zu, da eine Fütterung und Tränkung des Hundes ohne Gefährdung des Personals kaum möglich war, wie bereits die Erfahrung aus einem früheren Aufenthalt gezeigt hatte. Angesichts seines Wesens als Schutzhund hätte nur der Beschwerdeführer die Situation entschärfen können. Dieser weilte allerdings in den Ferien, und seine Ehefrau wollte nach dem Vorfall nichts mehr mit dem Hund zu tun haben und hatte auch - wie der Angriff auf die Velofahrerin gezeigt hatte - nicht die gewünschte Herrschaft über das Tier. Inso-fern war auch die zeitliche Dringlichkeit gegeben. Zudem stehen - wie bereits ausgeführt - keine geeigneten gesetzlichen Massnahmen zur Verfügung. Die polizeiliche Generalklausel vermochte deshalb die fehlende gesetzliche Grundlage zur Einschränkung der Eigentumsfreiheit des Beschwerdeführers zu ersetzen. Auch das öffentliche Interesse zum Schutz der fundamentalen Rechtsgüter Leben und Gesundheit steht ausser Frage.
2.3.2.3 Zu prüfen ist deshalb, ob die Euthanasierung des Hundes verhältnismässig gewesen ist. Das verfassungsmässige Gebot der Verhältnismässigkeit verlangt, dass staatliche Hoheitsakte für das Erreichen eines im übergeordneten öffentlichen Interesse liegenden Zieles geeignet, notwendig und dem Betroffenen zumutbar sein müssen. Eine Massnahme ist namentlich dann unverhältnismässig, wenn eine ebenso geeignete mildere Anordnung für den angestrebten Erfolg ausreicht. Das bereits Ausgeführte erhellt, dass die Euthanasierung des Hundes geeignet und auch erforderlich gewesen war: so standen keine milderen Massnahmen zur Verfügung, um die unmittelbare Gefahr abzuwenden. Insbesondere auch das längere Halten des Hundes in einem Zwinger stellt nur scheinbar eine mögliche taugliche Massnahme dar, denn bei jeder Fütterung und Tränkung erneuert sich die Gefahr für das Leben des Personals. Dabei ist der Verzicht auf die Befriedigung der Grundbedürfnisse des Hundes lediglich über wenige Stunden möglich und stellt keine langfristige Lösung dar; zudem würde dadurch auch der Grundsatz von Art. 2 Abs. 1 aTSchG, wonach Tiere so zu behandeln sind, dass ihren Bedürfnissen in bestmöglicher Weise Rechnung getragen wird, verletzt. Schliesslich sind auch Arzneimittel, welche den Hund ruhig stellen würden, keine langfristigen Alternativen. Abgesehen davon wäre bereits die Verabreichung eines Beruhigungsmittel nicht ungefährlich. Zu berücksichtigen ist ebenfalls, dass aufgrund der Erfahrungen aus dem früheren Aufenthalt des Hundes im Tierheim, zusammen mit den Ereignissen rund um den Vorfall mit der Velofahrerin, der Tierarzt davon ausgehen konnte, dass selbst nach der Ruhigstellung des Hundes dies sein Wesen nicht ändern würde. Die Massnahme war sodann auch zumutbar. Zwar wurde auf der einen Seite das Eigentum des Beschwerdeführers vernichtet. Auf der anderen Seite stand allerdings das fundamentale Rechtsgut des Lebens und der Gesundheit. Angesichts der unmittelbaren Gefahr mit dem grossen, massigen, 60 kg schweren, unmotiviert aggressiven Hund, der zudem nur den abwesenden Beschwerdeführer als seinen Meister akzeptierte, bestand ein offensichtliches Missverhältnis zwischen dem gewichtigen öffentlichen Interesse am Schutz der Allgemeinheit vor dem gefährlichen Hund und dem privaten Interesse am Eigentum des Beschwerdeführers (vgl. <ref-ruling> E. 4.2 S. 257). Die Euthanasierung war somit verhältnismässig.
3. 3.1 Die Beschwerde ist demnach abzuweisen, soweit darauf eingetreten wird.
3.2 Dem Verfahrensausgang entsprechend hat der unterliegende Beschwerdeführer die Gerichtskosten zu tragen (Art. 66 Abs. 1 und Art. 65 BGG). Eine Parteientschädigung ist nicht geschuldet (Art. 68 Abs. 3 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 2'500.-- werden dem Beschwerdeführer auferlegt.
3. Dieses Urteil wird den Verfahrensbeteiligten und dem Verwaltungsgericht des Kantons Graubünden, 1. Kammer, schriftlich mitgeteilt.
Lausanne, 30. November 2009
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Müller Errass