Faits:
A. Le chien "C._" est un dogue argentin, mis bas le 6 décembre 2002 et castré en février 2006. Le 16 octobre 2006, B.X._ a obtenu du vétérinaire cantonal l'autorisation spéciale délivrée pour la détention de chien potentiellement dangereux en Valais. A une date non déterminée, B.X._ a confié le chien à son père, A.X._.
Le 18 mais 2007, A.X._ ainsi que D._ ont été mordus par "C._". D._ a été mordu au visage et à la jambe: la morsure au visage a causé une perte de substance de la lèvre, une fracture du nez avec atteinte au cartilage et des plaies punctiformes; la morsure au mollet a causé une lacération musculaire, une plaie cutanée béante de 8 sur 5 cm. et laissé un chéloïde sur toute la longueur, la perte de substance restant visible; les morsures à la cheville ont laissé neuf plaies perforantes de 1 à 8 cm. Le 18 mai 2007 également, A.X._ a subi des blessures à deux doigts. Averti par le médecin traitant de D._, le vétérinaire cantonal a invité A.X._ à compléter un questionnaire sur les événements et à faire expertiser "C._" par une vétérinaire comportementaliste.
Dans son rapport d'expertise du 31 août 2007, après avoir décrit l'agression subie par D._ et relaté les résultats des examens auxquels elle avait procédé sur "C._", la vétérinaire relevait en substance que les blessures de ce dernier étaient graves, que celles de A.X._ du même jour, qui n'avaient pas été mentionnées, l'étaient aussi, que le comportement du chien atteignait 196 points sur l'échelle de dangerosité, ce qui dépassait la limite de 150 au delà de laquelle il constituait un risque mortel. Les faits dénotaient "une agression compétitive hiérarchique, mais non structurée, non contrôlée. D'après les conséquences, on [pouvait] parler d'hyperagression, c'est-à-dire d'une perturbation grave dans le fonctionnement du chien avec une phase d'attaque violente". Compte tenu de "l'irresponsabilité totale du propriétaire, [de son] inconscience des risques encourus par l'entourage, [de sa] méconnaissance des règles élémentaire de sécurité, l'euthanasie [était] vivement recommandée".
Le 13 septembre 2007, le vétérinaire cantonal a ordonné au détenteur d'euthanasier dans les trente jours son dogue argentin. Une éventuelle réclamation serait dépourvue d'effet suspensif.
Le 11 octobre 2007, A.X._ a interjeté une réclamation, offrant de suivre des cours d'éducation canine de six mois, à la fin desquels devrait être menée une nouvelle expertise. Il était en outre devenu propriétaire du chien et était prêt à poser un double grillage autour de sa propriété. Il a produit un rapport d'expertise de E._, vétérinaire comportementaliste qui corroborait l'opinion de l'expert nommée par le vétérinaire cantonal et détaillait les mesures qui devraient être prises si ce dernier modifiait sa décision. Le 20 novembre 2007, le vétérinaire cantonal a partiellement admis la réclamation. Il a maintenu l'ordre d'euthanasie en l'assortissant de prescriptions de sécurité à respecter jusqu'à l'exécution.
Un recours déposé auprès du Conseil d'Etat du canton du Valais a été rejeté par décision du 12 août 2008. Une évaluation comportementale du 13 décembre 2007 montrait que, malgré une thérapie intensive, les progrès étaient lents, que de grosses lacunes d'autocontrôle subsistaient et que le maître ne maîtrisait qu'imparfaitement le chien.
Une nouvelle agression a eu lieu le 25 février 2008. Le chien, qui portait une muselière et était en laisse, a provoqué une écorchure ou une éraflure à la tête d'un tiers. Par courrier du 10 mars 2008, le vétérinaire cantonal a invité A.X._ à se déterminer à ce sujet. Le 1er avril 2008, il a également avisé le Conseil d'Etat, qui a communiqué cette lettre au recourant le 4 avril.
Le 23 septembre 2008, A.X._ a recouru auprès du Tribunal cantonal contre la décision rendue le 12 août 2008 par le Conseil d'Etat. Il n'a pas évoqué l'agression du 25 février 2008 dans son mémoire de recours.
B. Par arrêt du 7 novembre 2008, le Tribunal cantonal a rejeté le recours. A.X._ n'ayant pas évoqué l'agression du 25 février 2008 dans son recours, ce fait était tenu pour avéré. Les expertises privées versées au dossier étant antérieures au 25 février 2008, leur contenu ne permettait pas de se distancier de l'expertise du 31 août 2007. Cette expertise était fiable; elle avait pronostiqué une réitération, ce qui avait été vérifié. Il n'y avait pas lieu de procéder à une expertise supplémentaire.
C. Agissant par la voie du recours constitutionnel subsidiaire, A.X._ demande au Tribunal fédéral sous suite de frais et dépens, d'annuler l'arrêt rendu le 7 novembre 2008 par le Tribunal cantonal. Il se plaint de la constatation inexacte des faits, de la violation du principe de proportionnalité ainsi que de son droit d'être entendu. Il demande l'octroi de l'effet suspensif.
Le Tribunal cantonal renonce à déposer des observations. Le Conseil d'Etat conclut au rejet du recours sous suite de frais.

Considérant en droit:
1. 1.1 Le recourant a déclaré former un recours constitutionnel subsidiaire contre l'arrêt du Tribunal cantonal du 11 juillet 2008. L'intitulé erroné du recours ne saurait pourtant préjuger de la voie ouverte, ni porter préjudice au recourant, pour autant que son écriture remplisse les conditions formelles de la voie de droit qui s'impose (au sujet d'une voie erronée de recours, <ref-ruling> consid. 1.2 p. 302 s., 308 consid. 4.1 p. 314).
1.2 Dirigé contre un arrêt rendu dans une cause de droit public (<ref-law>) par une autorité cantonale de dernière instance (art. 86 al. 1 let. d LTF), le recours ne tombe pas sous le coup d'une des exceptions mentionnées à l'<ref-law>.
1.3 Déposé en temps utile (<ref-law>) et, sous réserve des questions de motivation, dans les formes prescrites par la loi (<ref-law>), par le destinataire de l'arrêt attaqué qui a un intérêt digne de protection à l'annulation ou à la modification de celui-ci (<ref-law>), il est en principe recevable comme recours en matière de droit public, ce qui exclut la voie du recours constitutionnel subsidiaire (<ref-law>).
2. 2.1 Le Tribunal fédéral conduit son raisonnement juridique sur la base des faits établis par l'autorité précédente (cf. <ref-law>). Il peut néanmoins rectifier ou compléter les faits constatés de façon manifestement inexacte (soit arbitraire; <ref-ruling> consid. 7.1 p. 398) ou en violation du droit au sens de l'<ref-law> (cf. <ref-law>). Le recourant peut soulever de tels vices relatifs à la constatation des faits si leur correction est susceptible d'influer sur le sort de la cause (cf. <ref-law>); toutefois, dans la mesure où il se plaint d'arbitraire dans la constatation des faits ou d'application inconstitutionnelle de règles de procédure cantonale, il est tenu de se conformer aux exigences de motivation prévues à l'<ref-law>, soit d'exposer d'une manière circonstanciée ses griefs (cf. <ref-ruling> consid. 1.4.3 p. 254 ss).
2.2 Selon l'<ref-law>, le recours (ordinaire) au Tribunal fédéral peut être formé notamment pour violation du droit fédéral (let. a), qui comprend les droits constitutionnels des citoyens. En revanche, sauf exceptions non pertinentes en l'espèce (cf. art. 95 let. c à e LTF), la mauvaise application des dispositions cantonales ne peut pas être attaquée directement comme telle devant le Tribunal fédéral (<ref-law> a contrario). Il est néanmoins possible de faire valoir que leur mise en oeuvre consacre une violation du droit fédéral, comme la protection contre l'arbitraire au sens de l'art. 9 Cst. ou la garantie d'autres droits constitutionnels (cf. <ref-ruling> consid. 2.3 p. 466). Le Tribunal fédéral n'examine cependant de tels moyens que s'ils sont formulés conformément aux exigences de motivation qualifiées prévues à l'<ref-law>, qui valent en particulier pour le grief d'arbitraire (cf. <ref-ruling> consid. 2 p. 639 s.; <ref-ruling> consid. 1.4.2 p. 254).
3. Le recourant soutient en premier lieu que le Tribunal cantonal aurait constaté les faits de manière inexacte en retenant qu'une nouvelle agression avait eu lieu le 25 février 2008.
Il n'expose pas en quoi les constatations du Tribunal cantonal entreraient en contradiction manifeste entre elles ou avec les pièces qui figuraient au dossier cantonal. Il ne cite aucune disposition de droit cantonal ni aucune garantie constitutionnelle qui auraient été, le cas échéant, violées par le Tribunal cantonal dans l'établissement des faits. Les critiques qu'il formule se bornent à opposer sa version des faits à celle retenue par le Tribunal cantonal. Son grief est dès lors irrecevable. Il n'est par conséquent pas possible de tenir compte sur ce point d'un état de fait qui diverge de celui retenu dans l'arrêt attaqué.
4. Le recourant soutient que le Tribunal cantonal a violé le principe de proportionnalité ainsi que l'art. 24b al. 7 et al. 10 de la loi cantonale d'application de la loi fédérale sur la protection des animaux du 14 novembre 1984 (LcLPA; RSVS 455.1), selon lequel le Service vétérinaire détermine si l'animal doit être qualifié de dangereux pour l'homme, si son comportement est corrigible par une formation adéquate et décide de son euthanasie si le comportement du chien est jugé incorrigible.
Le principe de la proportionnalité figurant à l'art. 5 al. 2 Cst. n'est pas un droit fondamental, mais simplement un principe constitutionnel. Comme le recours en matière de droit public peut être formé pour violation du droit fédéral en général (<ref-law>), il est possible d'invoquer le principe de la proportionnalité directement et indépendamment d'un droit fondamental (<ref-ruling> consid. 4.1 p. 156 s. et les références). Le Tribunal fédéral a toutefois précisé que, lorsqu'il examine le droit cantonal indépendamment de toute atteinte à un droit fondamental, il ne revoit pas le respect du principe de la proportionnalité librement, mais seulement sous l'angle de l'arbitraire (<ref-ruling> consid. 4.3 p. 158).
Comme le recourant n'invoque aucun autre droit fondamental à l'appui de son grief, l'atteinte au principe de la proportionnalité alléguée en l'espèce se confond donc avec le grief d'arbitraire. La violation de l'interdiction de l'arbitraire ne peut être examinée que si sa motivation est conforme aux exigences de l'<ref-law> (cf. consid. 2.1 ci-dessus). Tel n'est pas le cas ici, puisque le recourant se borne à affirmer qu'une telle violation existe sans en donner les raisons.
5. Invoquant l'art. 29 al. 2 Cst., le recourant se plaint de ce que le Tribunal cantonal a violé son droit de faire administrer les preuves en refusant d'ordonner une contre-expertise.
5.1 Le droit d'être entendu, tel qu'il est garanti par l'art. 29 al. 2 Cst., comprend le droit pour l'intéressé de s'exprimer sur les éléments pertinents avant qu'une décision ne soit prise touchant sa situation juridique, de produire des preuves pertinentes, d'obtenir qu'il soit donné suite à ses offres de preuves pertinentes, de participer à l'administration des preuves essentielles ou à tout le moins de s'exprimer sur son résultat, lorsque cela est de nature à influer sur la décision à rendre (<ref-ruling> consid. 3.1 p. 277). La garantie constitutionnelle du droit de faire administrer des preuves n'empêche toutefois pas l'autorité de mettre un terme à l'instruction lorsque les preuves administrées lui ont permis de former sa conviction et que, procédant d'une manière non arbitraire à une appréciation anticipée des preuves qui lui sont encore proposées, elle a la certitude que celles-ci ne pourraient l'amener à modifier son opinion (<ref-ruling> consid. 2.1 p. 429; <ref-ruling> consid. 5b/bb p. 505/506).
5.2 Le Tribunal cantonal a jugé que le contenu des rapports d'expertise des Dr. E._ et F._ corroboraient l'opinion de l'experte mandatée par le vétérinaire cantonal (arrêt attaqué, p. 6), qu'ils avaient été établis avant le 25 février 2008 et qu'ils ne justifiaient pas de se distancier de l'expertise 31 août 2007, dont le contenu était confirmé par l'agression du 25 février 2008. Il en a conclu qu'une nouvelle expertise était inutile à l'établissement des faits pertinents.
Le recourant objecte que "depuis la survenance des événements, le chien C._ a suivi des cours d'éducation intensifs et, selon les déclarations des professionnels qui l'ont entouré, son comportement a évolué positivement". Ce faisant, il n'expose pas en quoi le Tribunal cantonal a procédé à une appréciation arbitraire des preuves. Il s'écarte en outre des faits retenus par le Tribunal cantonal, qui lient le Tribunal fédéral (cf. consid. 3 ci-dessus) et fait valoir des faits nouveaux irrecevables (<ref-law>). Son grief est irrecevable.
6. Les considérants qui précédent conduisent à l'irrecevabilité du recours, considéré comme recours en matière de droit public. Il s'ensuit que la requête d'effet suspensif déposée par le recourant n'a plus d'objet. Succombant, le recourant doit supporter un émolument judiciaire (art. 65 et 66 LTF). Il n'a pas droit à des dépens (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours, considéré comme recours en matière de droit public, est irrecevable.
2. La requête d'effet suspensif est sans objet.
3. Les frais judiciaires, arrêtés à 2'000 fr., sont mis à la charge du recourant.
4. Le présent arrêt est communiqué au mandataire du recourant, au Vétérinaire cantonal, au Conseil d'Etat et à la Cour de droit public du Tribunal cantonal du canton du Valais.
Lausanne, le 28 janvier 2009
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: Le Greffier:
Müller Dubey