Faits:
A. X._, né le 12 septembre 1952, est arrivé en Suisse en 1989 et a travaillé comme médecin dépendant dans le canton du Valais. Ayant obtenu le diplôme fédéral de médecin le 13 septembre 2002, le Département de la santé, des affaires sociales et de l'énergie du canton du Valais (devenu Département des finances, des institutions et de la santé, ci-après: le Département) lui a délivré une autorisation de pratiquer la médecine à titre indépendant. Depuis lors, il a exercé sa profession principalement à A._.
A.a Le 23 juillet 2007, l'Office du juge d'instruction cantonal valaisan a ouvert une instruction pénale contre X._ et B._, pharmacien à C._, pour escroquerie et faux dans les certificats, subsidiairement pour faux certificat médical. Il était reproché à X._ d'avoir établi de fausses ordonnances médicales, afin de permettre à des patients qui se rendaient chez le pharmacien B._ de bénéficier de produits pharmaceutiques sans bourses délier, les coûts étant mis indûment à la charge de l'assurance obligatoire. X._ a été placé en détention préventive du 9 octobre au 21 décembre 2007. A ce jour, l'instruction pénale est toujours en cours. Dans ce cadre, un rapport d'expertise psychiatrique de l'intéressé a été établi le 16 octobre 2008.
A.b Le 12 février 2008, le chef du Département a retiré l'autorisation de pratiquer de X._ à titre de mesure provisionnelle. Celui-ci a recouru contre ce prononcé auprès du Conseil d'Etat du canton du Valais. Le retrait de l'effet suspensif au recours administratif a été confirmé, le 16 mai 2008, en dernière instance cantonale. Dans le cadre de la procédure disciplinaire, un rapport d'expertise a été déposé, le 27 mars 2010, par D._, Professeur à la Division pharmacologie et toxicologique du CHUV, à Lausanne. Le 12 mai 2010, la Cour de droit public du Tribunal cantonal du canton du Valais (ci-après: le Tribunal cantonal) a annulé la décision incidente du 23 février 2010 qui suspendait l'instruction de la cause jusqu'à droit connu sur la procédure pénale. Par arrêt du 29 avril 2011, elle a aussi admis le recours de X._ pour déni de justice et renvoyé le dossier au Conseil d'Etat pour qu'il statue sur la mesure provisionnelle.
A.c La procédure sur le prononcé d'une sanction disciplinaire s'est poursuivie. Après avoir entendu X._ le 22 juin 2010, la Commission de surveillance des professions de la santé du canton du Valais a rendu son préavis le 4 avril 2011.
Par décision du 15 avril 2011, le Département a prononcé le retrait définitif de l'autorisation de pratiquer de X._ comme médecin indépendant. Il a retenu en bref que ce dernier avait gravement violé ses devoirs professionnels sur une longue période (2003 à 2007) en mettant sur pied une pratique avec le pharmacien B._, qui avait permis à de nombreux patients de bénéficier de médicaments de substitution aux fins de faire supporter par l'assurance obligatoire des soins les coûts de produits non couverts par cette assurance et en établissant des ordonnances pour des médicaments destinés à des tiers, souvent des membres de la famille résidant à l'étranger. Ces procédés avaient eu pour résultat de délivrer des médicaments susceptibles de générer des effets secondaires importants et qui ne pouvaient être prescrits sans suivi médical. Ces violations justifiaient d'appliquer au médecin la sanction la plus sévère, dès lors que l'expertise psychiatrique du 16 octobre 2008 révélait que le risque de récidive n'était pas exclu au vu de la personnalité de l'intéressé.
B. X._ a recouru contre cette décision auprès du Conseil d'Etat qui, le 26 octobre 2011, a rejeté le recours. Il a notamment considéré qu'au vu des manquements graves de l'intéressé à ses obligations professionnelles et de son absence totale de prise de conscience de la gravité de ses actes, la sanction litigieuse n'était pas disproportionnée.
Saisi d'un recours de X._ contre ce prononcé, le Tribunal cantonal l'a rejeté par arrêt du 19 avril 2012. Il s'est fondé essentiellement sur les manquements aux devoirs professionnels constatés dans l'expertise du Prof. D._, mais s'est écarté de la solution proposée par ce dernier tendant à la reprise d'une activité médicale indépendante subordonnée à des mesures de contrôle.
C. Agissant par la voie du recours en matière de droit public, X._ conclut, sous suite de frais et d'une indemnité de 5'000 fr. à titre de dépens, à l'annulation de l'arrêt du Tribunal cantonal du 19 avril 2012 et à la confirmation de son autorisation de pratiquer à titre indépendant comme médecin. Le recourant a également présenté une demande d'assistance judiciaire, qu'il a ensuite retirée par lettre du 13 juillet 2012, après avoir versé l'avance de frais requise.
Le Tribunal cantonal a renoncé à se déterminer sur le recours. Le Conseil d'Etat et le Département se rallient aux considérants de l'arrêt attaqué et concluent au rejet du recours.
D. Par ordonnance présidentielle du 2 juillet 2012, la requête d'effet suspensif contenue dans le recours a été rejetée.

Considérant en droit:
1. Le recours est dirigé contre un jugement final (<ref-law>) rendu dans une cause de droit public (cf. <ref-law>) par un tribunal cantonal supérieur (art. 86 al. 1 let. d et al. 2 LTF), sans que l'on se trouve dans l'un des cas d'exceptions mentionnés par l'<ref-law>. Déposé en outre dans le délai (art. 46 al. 1 let. c et 100 al. 1 LTF) et en la forme (<ref-law>) prévus par la loi, par le recourant qui est atteint par la décision entreprise et a un intérêt digne de protection à son annulation ou à sa modification (<ref-law>), il est en principe recevable comme recours en matière de droit public.
2. Saisi d'un recours en matière de droit public, le Tribunal fédéral examine librement la violation du droit fédéral, qui comprend les droits de nature constitutionnelle (cf. art. 95 let. a et 106 al. 1 LTF), sous réserve des exigences de motivation figurant à l'<ref-law>. Il y procède en se fondant sur les faits constatés par l'autorité précédente (cf. <ref-law>), à moins que ces faits n'aient été établis de façon manifestement inexacte ou en violation du droit au sens de l'<ref-law> (cf. <ref-law>). La notion de "manifestement inexacte" de l'<ref-law> correspond à celle d'arbitraire de l'art. 9 Cst. (<ref-ruling> consid. 2.1 p. 450 ; <ref-ruling> consid. 7.1 p. 398). Le recourant doit ainsi expliquer de manière circonstanciée en quoi les conditions d'une exception prévue par l'<ref-law> seraient réalisées, faute de quoi il n'est pas possible de tenir compte d'un état de fait qui diverge de celui qui est contenu dans l'acte attaqué.
En l'espèce, le recourant ne critique pas l'état de fait retenu dans l'arrêt entrepris, mais se plaint de la durée de la procédure disciplinaire qui lui a valu d'être suspendu provisoirement de son activité indépendante de médecin pendant plus de trois ans (du 12 février 2008 au 15 avril 2011), ce qu'il estime largement suffisant pour sanctionner son comportement. Au fond, il reproche au Tribunal cantonal de s'être borné à confirmer la mesure provisionnelle, en s'écartant sans motif valable du rapport d'expertise du Prof. D._. L'interdiction définitive de pratiquer prononcée contre lui ne répondrait ainsi à aucun intérêt public prépondérant et violerait le principe de la proportionnalité. La juridiction cantonale aurait en outre violé le principe de la présomption d'innocence en se fondant sur le dossier pénal.
3. 3.1 La loi fédérale sur les professions médicales universitaires du 23 juin 2006, entrée en vigueur le 1er septembre 2007, a pour but d'unifier le droit disciplinaire en prévoyant des mesures uniformes en cas de violation des obligations professionnelles (cf. Message du 3 décembre 2004, FF 2005 p. 212). Sous le titre "devoirs professionnels", l'<ref-law> contient une disposition générale imposant aux personnes exerçant une profession médicale universitaire à titre indépendant d'exercer leur activité "avec soin et conscience professionnelle", sans plus de précision. L'<ref-law> énumère les mesures disciplinaires possibles en cas de violation des devoirs professionnels, soit notamment, l'interdiction de pratiquer à titre indépendant pendant six ans au plus (interdiction temporaire; let. d) et l'interdiction définitive de pratiquer à titre indépendant pour tout ou partie du champ d'activité (let. e). L'art. 133 de la loi valaisanne sur la santé du 14 février 2008 (LS; RS VS 800.1) a la même teneur et renvoie au droit fédéral en ce qui concerne le contenu des droits et des devoirs professionnels (art. 73 LS). Les dispositions du nouveau droit ont été appliquées au recourant, dans la mesure où elles ont été jugées plus favorables que celles de l'ancienne loi sur la santé publique du 9 février 1996, ce qui est conforme au principe de la lex mitior de l'<ref-law>, applicable en matière de sanctions disciplinaires (arrêts 2C_34/2011 du 30 juillet 2011, consid. 6.1 et 2A.448/2003 du 3 août 2004, consid. 1.4).
3.2 Le retrait définitif de l'autorisation de pratiquer à titre indépendant, prononcé à l'encontre du recourant en application des art. 43 al. 1 let. e LPMéd et 133 al. 1 let. e LS, constitue une restriction grave à sa liberté économique. Le Tribunal fédéral examine librement et avec plein pouvoir d'examen si l'exigence de l'intérêt public (art. 36 al. 2 Cst.) et le principe de la proportionnalité (cf. art. 36 al. 3 Cst.) sont respectés (<ref-ruling> consid. 3a p. 217; <ref-ruling> consid. 4a p. 244 et les références citées). Il laisse cependant une certaine liberté à l'autorité disciplinaire dans le choix de la sanction à prononcer, à condition qu'elle respecte le principe de la proportionnalité (<ref-ruling> consid. 13c p. 121).
3.3 Les mesures disciplinaires infligées à un membre d'une profession libérale soumise à la surveillance de l'Etat ont principalement pour but de maintenir l'ordre dans la profession, d'en assurer le fonctionnement correct, d'en sauvegarder le bon renom et la confiance des citoyens envers cette profession, ainsi que de protéger le public contre ceux de ses représentants qui pourraient manquer des qualités nécessaires. Les mesures disciplinaires ne visent pas, au premier plan, à punir le destinataire, mais à l'amener à adopter à l'avenir un comportement conforme aux exigences de la profession et à rétablir le fonctionnement correct de celle-ci. En ce sens, les sanctions disciplinaires se distinguent des sanctions pénales. De plus, le principe de la proportionnalité doit être examiné à l'aune des intérêts publics précités. Ainsi, le choix de la nature et de la quotité de la sanction doit être approprié au genre et à la gravité de la violation des devoirs professionnels et ne pas aller au-delà de ce qui est nécessaire pour assurer les buts d'intérêt public recherchés. A cet égard, l'autorité doit tenir compte en premier lieu d'éléments objectifs, à savoir des conséquences que la faute a entraînées sur le bon fonctionnement de la profession en cause, et de facteurs subjectifs, tels que la gravité de la faute, ainsi que les mobiles et les antécédents de l'intéressé (<ref-ruling> consid. 2b; <ref-ruling> consid. 13c p. 121; <ref-ruling> consid. 2b; <ref-ruling> consid. 2a; arrêt 2P.133/2003 du 28 juillet 2003, consid. 4.2.1 et les références citées). Une interdiction définitive de pratiquer ne doit en principe être prononcée que si, au regard de l'ensemble de l'activité professionnelle exercée par l'intéressé, une autre sanction apparaît insuffisante pour assurer un comportement correct à l'avenir (<ref-ruling> consid. 13c p. 126/127; BORIS ETTER, Medizinalberufsgesetz, 2006, n. 18 ad art. 43, p. 138).
3.4 L'enquête disciplinaire a démontré que le recourant avait violé de façon répétée et systématique plusieurs de ses obligations professionnelles. Outre la remise d'ordonnances vierges et la prescription de médicaments de substitution pour mettre leur coût à la charge de l'assurance de base, l'expert a relevé la tenue inadéquate et lacunaire des dossiers de la grande majorité des patients. Indépendamment de la procédure pénale toujours pendante, les manquements professionnels commis par le recourant, tels que constatés dans le cadre de la procédure disciplinaire, sont graves et justifient une sanction disciplinaire. Compte tenu de la nature de ces manquements qui, contrairement à ce que prétend le recourant, mettaient en cause la sécurité des patients et représentaient un facteur de risque pour leurs traitements, il y a également un intérêt public certain à prononcer une mesure visant à garantir le bon fonctionnement de la profession. Reste à examiner si en prononçant la sanction disciplinaire la plus grave, les autorités cantonales ont respecté le principe de la proportionnalité.
3.4 L'enquête disciplinaire a démontré que le recourant avait violé de façon répétée et systématique plusieurs de ses obligations professionnelles. Outre la remise d'ordonnances vierges et la prescription de médicaments de substitution pour mettre leur coût à la charge de l'assurance de base, l'expert a relevé la tenue inadéquate et lacunaire des dossiers de la grande majorité des patients. Indépendamment de la procédure pénale toujours pendante, les manquements professionnels commis par le recourant, tels que constatés dans le cadre de la procédure disciplinaire, sont graves et justifient une sanction disciplinaire. Compte tenu de la nature de ces manquements qui, contrairement à ce que prétend le recourant, mettaient en cause la sécurité des patients et représentaient un facteur de risque pour leurs traitements, il y a également un intérêt public certain à prononcer une mesure visant à garantir le bon fonctionnement de la profession. Reste à examiner si en prononçant la sanction disciplinaire la plus grave, les autorités cantonales ont respecté le principe de la proportionnalité.
3.5 3.5.1 Le Tribunal cantonal a jugé qu'une interdiction temporaire de pratiquer ne suffirait pas à amener le recourant à adopter à l'avenir un comportement conforme aux exigences de sa profession, dans la mesure où ce dernier ne semblait ni enclin, ni apte à se remettre en question et à apprécier la portée des manquements qui lui étaient reprochés. Quant à la possibilité évoquée par l'expert de permettre au recourant de reprendre une activité médicale indépendante en soumettant le praticien à des conditions propres à exclure le risque de récidive, la juridiction cantonale l'a écartée, en estimant que le succès des mesures à prendre paraissait incertain au vu de la personnalité de l'intéressé et qu'on pouvait dès lors se demander s'il était raisonnable d'imposer cette charge à l'administration. A cela s'ajoutait que la solution préconisée par l'expert reviendrait « à mettre le recourant, probablement durant plusieurs années, sous la responsabilité d'un ou de plusieurs autres praticiens », de sorte que la reprise d'une activité indépendante ne pourrait intervenir qu'à une époque où l'intéressé, né en 1952, serait proche de l'âge ordinaire de la retraite (arrêt attaqué p. 11).
De son côté, le recourant relève que le Tribunal cantonal s'est borné à confirmer la mesure provisionnelle du Département, devenue définitive après plus de trois ans, sans prendre en compte les autres possibilités de l'<ref-law> ou celles proposées par le Prof. D._ et sans démontrer pourquoi il ne pourrait pas adopter à l'avenir un comportement conforme aux exigences de la profession. Il fait en outre valoir que le retrait définitif de son autorisation de pratiquer à titre indépendant entraîne pour lui de graves conséquences, tant sur le plan financier, qu'au niveau moral, alors qu'il n'a jamais mis en péril la santé de ses patients.
3.5.2 Il n'est pas contesté que le recourant n'a pas d'antécédents disciplinaires et qu'il n'a pas non plus fait l'objet de plaintes de la part de ses patients qui, pour la plupart, ont plutôt bénéficié financièrement des pratiques qu'il avait mises en place avec le pharmacien B._. Malgré cette absence d'antécédents, le Département a d'emblée prononcé le retrait provisoire de l'autorisation de pratiquer sans conditions et a attendu quatorze mois après sa décision du 12 février 2008, avant de confier au Prof. D._ la mission d'évaluer dans quelle mesure le recourant présentait, tant physiquement que psychiquement, les garanties nécessaires à un exercice irréprochable de la profession au sens de l'<ref-law> (voir rapport d'expertise du 27 mars 2010 p. 1); il a finalement prononcé le retrait définitif de l'autorisation litigieuse, le 15 avril 2011. Dans son examen de la proportionnalité de la mesure disciplinaire infligée, le Tribunal cantonal n'a pas tenu compte de la durée de cette instruction de plus de trois ans, ni des conséquences du retrait définitif de l'autorisation de pratiquer du recourant (voir arrêt 2P.169/2004 du 7 février 2005 consid. 3.2, s'agissant d'un retrait d'une autorisation de pratiquer en tant que médecin de deux ans jugée disproportionnée compte tenu des mesures de contrôle déjà mises en place). A aucun moment il n'a examiné la situation personnelle du recourant sur le plan professionnel ou financier (sur ce dernier aspect, voir arrêt 2P.282/2003 du 19 mars 2004 consid. 3.2). Quant aux raisons invoquées pour s'écarter des conclusions du rapport d'expertise du Prof. D._ (difficultés de la mise en place de contrôles et âge du recourant), elles ne suffisent pas à convaincre que la reprise de l'activité du recourant comme médecin indépendant avec des mesures d'accompagnement serait forcément vouée à l'échec compte tenu de la personnalité de ce dernier. L'expert a en effet conclu qu'aucun problème physique ou psychique n'était susceptible d'interférer sérieusement dans la pratique médicale de l'intéressé. Il a cependant émis de sérieuses réserves en raison de l'hyperactivité du recourant et de son absence à mettre en doute ses capacités, ses compétences et son jugement médical. Ainsi, les graves et très nombreux manquements constatés étaient en partie explicables par une activité de consultation très importante et paraissaient a priori pouvoir être corrigés par une réduction de « patientèle ». Compte tenu des traits de la personnalité du recourant et du risque de répétition de pratiques médicales déviantes, il était nécessaire que la reprise du droit de pratiquer soit subordonnée à des mesures de contrôle: obligation de mise à jour de la formation et supervision régulière dans un cadre strict puis, si acceptées et réalisées avec succès, obligation d'un coaching sérieux (cf. rapport d'expertise du 27 mars 2010, « conclusions » pp. 12 à 14).
3.5.3 Au vu de cet examen, les premiers juges ne pouvaient se fonder que sur les manquements et les défauts de comportement du recourant pour en conclure que seul un retrait définitif de l'autorisation de pratiquer litigieuse était propre à assurer la protection de la santé publique, sans tenir compte des mobiles de l'intéressé et de son absence d'antécédents. Certes, les graves manquements du recourant dans l'exercice de sa profession, constatés sur une longue période, imposaient de retirer l'autorisation de pratiquer. Un tel retrait n'est donc pas critiquable en soi, mais les juges cantonaux ont arbitrairement prononcé la sanction la plus sévère, en déclarant définitive l'interdiction de pratiquer à titre indépendant. Ce faisant, ils ont préjugé de l'incapacité du recourant à se soumettre à des mesures de contrôle et ne lui ont donné aucune chance de pouvoir s'amender. Cette possibilité devait en effet être offerte au recourant, du moment que celui-ci n'avait aucun antécédent et qu'il n'a pas davantage manqué à ses devoirs dans l'intention de s'enrichir ou de porter préjudice à ses patients. Il n'appartenait pas non plus à la juridiction cantonale de tenir compte du fait que l'intéressé est actuellement âgé de soixante ans, dès lors qu'un médecin peut en principe poursuivre son activité jusqu'à l'âge de septante ans, puis présenter une demande de renouvellement de son autorisation tous les deux ans (cf. art. 12 de l'ordonnance du Conseil d'Etat du canton du Valais du 18 mars 2009 sur l'exercice des professions de la santé et leur surveillance: RS 811.100). Au regard de l'ensemble des circonstances, un retrait définitif de l'autorisation ne se justifie pas et apparaît dès lors comme une sanction disproportionnée. Quant à la durée du retrait qui pouvait être prononcée par rapport aux faits reprochés au recourant, il y a lieu de prendre en considération le fait que, par le jeu de l'effet suspensif et de la durée de la procédure devant les instances cantonales, le recourant a perdu son autorisation de pratiquer depuis le 12 février 2008, soit depuis plus de quatre ans et demi. Cette mesure peut donc à présent être levée et le recourant doit être autorisé à pratiquer à nouveau comme médecin à titre indépendant. Cela ne doit pas empêcher la mise en place de mesures de surveillance, puisqu'en tant que médecin, le recourant est de toute façon soumis au contrôle du département et de la Commission de surveillance des professions de la santé (cf. <ref-law>; 83 al. 3 LS et 29 al. 2 de l'ordonnance précitée du 18 mars 2009). Compte tenu du contexte et de la personnalité du recourant, ce contrôle devra être exercé strictement par les autorités compétentes, étant précisé que tout nouveau manquement entraînerait une nouvelle sanction.
4. Au vu de ce qui précède, le recours doit être admis dans le sens des considérants et l'arrêt attaqué annulé. L'autorisation de pratiquer comme médecin indépendant devra ainsi être restituée au recourant.
Le présent jugement sera rendu sans frais (<ref-law>). En revanche, le canton du Valais versera au recourant une indemnité à titre de dépens (<ref-law>), qu'il y a lieu de fixer conformément aux art. 1er et 2 du règlement sur les dépens alloués à la partie adverse et sur l'indemnité pour la représentation d'office dans les causes portées devant le Tribunal fédéral du 31 mars 2006 (RS 173.110.210.3), soit en tenant compte du dossier (art. 12) et non des prétentions émises par le mandataire du recourant, qui n'a du reste produit aucune note d'honoraires à cet effet. Il y a lieu également de renvoyer la cause au Tribunal cantonal pour fixation des frais et dépens de la procédure cantonale (art. 67 et 68 al. 5 LTF).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est admis dans le sens des considérants et l'arrêt attaqué est annulé.
2. L'autorisation de pratiquer comme médecin indépendant est restituée au recourant.
3. Il n'est pas perçu de frais judiciaires.
4. Le canton du Valais versera au recourant une indemnité de 3'000 fr. à titre de dépens.
5. L'affaire est renvoyée au Tribunal cantonal pour nouvelle décision sur les frais et dépens de la procédure cantonale.
6. Le présent arrêt est communiqué au mandataire du recourant, au Département des finances, des institutions et de la santé du canton du Valais, au Conseil d'Etat du canton du Valais, au Tribunal cantonal du canton du Valais, Cour de droit public, et au Département fédéral de l'intérieur.
Lausanne, le 22 novembre 2012
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: Zünd
La Greffière: Rochat