Faits:
A. A.a En 1984, X._ a été engagé par l'Hôpital Y._ en qualité de médecin-chef en anesthésie et en réanimation.
En sus de son activité de médecin-chef, X._ pouvait consacrer 10% de son temps à des activités académiques. Il était en outre membre du conseil de direction du département d'anesthésiologie et assumait la présidence de la commission d'urgence et, à partir de décembre 1995, la présidence du collège des médecins-chefs. X._ était également responsable du matériel lourd et à usage unique, des statistiques, de la facturation et du rapport annuel, et coresponsable de l'enseignement des médecins et infirmières.
Le 2 décembre 1998, les parties ont signé un nouveau contrat de travail, qui se distinguait du précédent notamment en ce qui concerne la réglementation de la couverture perte de gain en cas de maladie.
A.b Dans le contexte de la démission du Dr A._, médecin-chef anesthésiste, le comité de direction de l'Hôpital a pris la décision, en séance du 12 septembre 1995, de mettre en garde X._ en raison des critiques recueillies quant à ses sautes d'humeur et ses écarts de langage. Le comité a informé oralement X._ des griefs qui lui étaient faits.
X._ n'a cependant guère modifié ses habitudes et son naturel s'est encore affirmé au fil du temps. En décembre 2000, la direction a été informée de l'ampleur et de la gravité de la situation, à la lecture du rapport remis le 14 de ce mois par B._, chef du service du personnel. Ce rapport retranscrivait les plaintes des employés à l'endroit de X._.
A.c Le 23 décembre 2000, l'employeur a signifié à X._ son congé pour le 30 juin 2001, avec dispense immédiate de travailler.
X._ a été en incapacité de travail totale puis partielle du 26 décembre 2000 au 7 octobre 2001. Le 8 janvier 2001, l'employé a contesté la validité du congé.
L'Hôpital a versé le salaire de X._ jusqu'au 31 décembre 2001.
B. Le 16 novembre 2001, X._ a ouvert action devant le juge du district de ... à l'encontre de l'Association de l'Hôpital Y._. Il concluait à la condamnation de la défenderesse à lui verser la somme de 345'345 fr.30, avec intérêts dès le 3 janvier 2001, à titre de rétribution du travail supplémentaire (210'989 fr.40) et d'indemnité pour licenciement abusif (134'355 fr.90), et demandait à ce que le cas soit dénoncé aux autorités pénales compétentes. La défenderesse a proposé le rejet de la demande, dans la mesure de sa recevabilité.
L'instruction close, le dossier a été transmis à l'autorité de jugement. Statuant le 4 septembre 2007, la Cour civile II du Tribunal cantonal valaisan a rejeté la demande.
L'autorité cantonale a rejeté les prétentions du demandeur fondées sur 321c CO et considéré que la loi fédérale sur le travail dans l'industrie, l'artisanat et le commerce (LTr; 822.11) ne trouvait pas application. La juridiction cantonale a enfin nié le caractère abusif du licenciement.
C. Le demandeur interjette contre ce prononcé un recours en matière civile au Tribunal fédéral. Il conclut à l'admission du recours, à l'annulation du jugement entrepris et au renvoi de la cause au Tribunal cantonal pour nouvelle décision dans le sens des considérants.
La défenderesse sollicite le rejet du recours dans la mesure de sa recevabilité. Quant à l'autorité cantonale, elle se réfère aux considérants de son jugement.

Considérant en droit:
1. 1.1 Interjeté par la partie qui a succombé dans ses conclusions (<ref-law>) et dirigé contre un jugement final (<ref-law>) rendu en matière civile (<ref-law>) par une autorité cantonale de dernière instance (<ref-law>) dans une affaire pécuniaire concernant le droit du travail dont la valeur litigieuse atteint le seuil de 15'000 francs (<ref-law>), le recours en matière civile est en principe recevable, puisqu'il a été déposé dans le délai (<ref-law>) et la forme (<ref-law>) prévus par la loi.
1.2 Dans un recours en réforme comme le recours en matière civile, le recourant ne doit pas se borner à demander l'annulation de la décision attaquée, mais il doit également prendre des conclusions sur le fond du litige. Il n'est fait exception à cette règle que lorsque le Tribunal fédéral, en cas d'admission du recours, ne serait de toute manière pas en mesure de statuer lui-même sur le fond et devrait renvoyer la cause à l'autorité cantonale (<ref-ruling> consid. 3 et les arrêts cités; Bernard Corboz, Introduction à la nouvelle loi sur le Tribunal fédéral, in: SJ 2006 II 319 ss, p. 329 s.). En l'espèce, l'autorité cantonale n'a pas arrêté le nombre d'heures de travail supplémentaire effectuées par le recourant, puisqu'elle a retenu qu'aucun horaire de travail n'avait été convenu entre les parties. Cela étant, en cas d'admission du recours, la cause devra être renvoyée à l'instance cantonale pour qu'elle statue sur cette question. Dès lors, les conclusions cassatoires du recourant sont recevables.
1.3 Le recours peut être interjeté pour violation du droit, tel qu'il est délimité par les art. 95 et 96 LTF. Le Tribunal fédéral applique le droit d'office (<ref-law>). Il n'est donc limité ni par les arguments soulevés dans le recours ni par la motivation retenue par l'autorité précédente; il peut admettre un recours pour un autre motif que ceux qui ont été invoqués et il peut rejeter un recours en adoptant une argumentation différente de celle de l'autorité précédente (cf. <ref-ruling> consid. 1.4). Compte tenu de l'exigence de motivation contenue à l'art. 42 al. 1 et 2 LTF, sous peine d'irrecevabilité (<ref-law>), le Tribunal fédéral n'examine en principe que les griefs invoqués; il n'est pas tenu de traiter, comme le ferait une autorité de première instance, toutes les questions juridiques qui se posent, lorsque celles-ci ne sont plus discutées devant lui. Il ne peut pas entrer en matière sur la violation d'un droit constitutionnel ou sur une question relevant du droit cantonal ou intercantonal si le grief n'a pas été invoqué et motivé de manière précise par la partie recourante (<ref-law>). Cette exigence de motivation est calquée sur ce qui était exigé par la jurisprudence en matière de recours de droit public sur la base de l'art. 90 al. 1 let. b OJ (<ref-ruling> consid. 1.4; <ref-ruling> consid. 6 et l'arrêt cité).
1.4 Le Tribunal fédéral conduit son raisonnement juridique sur la base des faits établis par l'autorité précédente (<ref-law>). Il ne peut s'en écarter que si les faits ont été établis de façon manifestement inexacte ou en violation du droit au sens de l'<ref-law> (<ref-law>).
La partie recourante qui entend s'écarter des constatations de l'autorité précédente doit 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 contenu dans la décision attaquée (<ref-ruling> consid. 6.2; cf. <ref-ruling> consid. 1.4). Aucun fait nouveau ni preuve nouvelle ne peut être présenté à moins de résulter de la décision de l'autorité précédente (<ref-law>).
2. A titre liminaire, il est précisé que le litige ne porte que sur la question du travail supplémentaire ou des heures supplémentaires, le caractère non abusif du licenciement n'étant plus remis en cause.
3. 3.1 Le recourant s'en prend tout d'abord à deux constatations de fait de l'autorité cantonale, en considérant qu'il est arbitraire d'avoir retenu que le recourant « élaborait son propre emploi du temps en collaboration avec ses collègues » et qu'il « fixait les horaires de travail des infirmiers et des médecins-assistants et répartissait le travail » ou « faisait le planning du personnel en fonction de ses affinités, attribuant les personnes qu'il appréciait le moins à un autre médecin ».
Selon le recourant, la première constatation est insoutenable, puisque contraire aux conditions-cadre du Groupement des établissements hospitaliers valaisans (Gehval), qui indiquent que si le cahier des charges des médecins-chefs est élaboré par les intéressés, ceux-ci proposent aux responsables de l'établissement leur cahier des charges et, le cas échéant, l'organisation de leur service. Il ajoute que l'instruction de la cause n'a pas porté sur l'emploi du temps ou les horaires des médecins-chefs et que le volume des opérations chirurgicales à effectuer excluait toute latitude dans l'établissement d'un « horaire de travail ».
Quant aux deux autres constatations, le recourant les conteste formellement, en affirmant qu'elles n'ont jamais fait l'objet d'une instruction, d'allégations ou d'offres de preuve des parties et qu'elles ne sont confirmées par aucun document contractuel ou d'organisation. Pour appuyer ses dires, il soutient, référence faite au ch. 5.1.2 de la pièce 4, qu'au sein du conseil de direction du département, la charge de l'organisation du personnel était du ressort du Dr C._.
3.2 Dans la mesure où, s'agissant de la première constatation litigieuse, le recourant fonde son argumentation sur un passage des conditions-cadre du Gehval qui a trait au cahier des charges des médecins-chefs, mais pas à leur emploi du temps, sa critique est sans consistance. Par ailleurs, quoi qu'en dise le recourant, le témoin D._, directeur de l'Hôpital au moment des faits, s'est exprimé sur la question de l'emploi du temps des médecins-chefs. Enfin, le recourant semble perdre de vue qu'il a été retenu par l'autorité cantonale que si le recourant n'avait pas d'horaire de travail imposé, sa liberté était en pratique limitée par la nécessité d'organiser son emploi du temps en collaboration avec ses collègues de manière à faire face aux besoins de l'Hôpital.
Quant aux deux autres constatations, on ne saurait dénier toute valeur probante aux divers documents constituants le dossier pénal, dès l'instant où ce dossier a été dûment versé en cause et où les dépositions figurant dans ce dossier, notamment en ce qui concerne la fixation par le recourant des horaires de travail du personnel, n'ont pas été contredites en cours de procédure par les personnes entendues à ce sujet. De plus, la pièce 4 ne corrobore en rien l'affirmation selon laquelle le Dr C._ avait la charge de l'organisation du personnel, puisqu'il est indiqué sous chiffre 6.1.2 (et non pas 5.1.2, qui n'existe pas) que « le Dr C._ est présent. La commission constate que l'organisation actuelle qui permet au Dr A._ d'œuvrer principalement aux Soins intensifs a apaisé la situation ».
En tout état de cause, force est d'admettre que les constatations litigieuses ne constituent que des éléments d'appréciation parmi bien d'autres sur lesquels les juges se sont basés pour reconnaître que le recourant exerçait une fonction dirigeante élevée. Dès lors que les autres éléments d'appréciation ne sont pas présentement remis en cause, les constatations sur lesquelles porte le litige ne sauraient être arbitraires dans le résultat, ce que le recourant ne démontre du reste pas.
Dans ces circonstances, le premier grief tombe à faux.
4. Sous l'intitulé « Quant à l'application de la LTr aux médecins-chefs », le recourant revient sur la non-application par l'autorité cantonale de la LTr pour trancher la prétention du travail supplémentaire.
Dans son grief, le recourant ne démontre pas en quoi l'autorité cantonale aurait violé le droit fédéral, plus particulièrement l'art. 3 let. d LTr en lien avec l'art. 9 OLT 1. Il ne prétend pas et encore moins n'établit, que les éléments sur lesquels s'est fondée l'autorité cantonale pour admettre que le recourant occupait une fonction dirigeante élevée ne constituent pas des critères décisifs au sens de la jurisprudence. Par ailleurs, lorsque le recourant affirme que « le travailleur doit être en réalité un organe de fait pour qu'il puisse être considéré comme un cadre à fonction dirigeante élevée », il fait une lecture erronée de la jurisprudence du Tribunal fédéral dont il se fait l'écho.
Pour arriver à la conclusion qu'il n'a jamais occupé une fonction dirigeante élevée, le recourant se contente en définitive de prendre appui sur un certain nombre de faits, qui divergent manifestement de ceux retenus par l'autorité cantonale. En cela, le grief est clairement irrecevable.
5. Le recourant fait enfin état d'une violation de l'<ref-law>.
5.1 La cour cantonale a considéré que le recourant ne pouvait pas fonder ses prétentions sur l'<ref-law>, au motif qu'il n'a pas été établi que les parties avaient convenu d'un horaire de travail de 45 heures par semaine, comme allégué par le recourant à l'appui de ses prétentions. Les juges ont retenu que la terminologie « 9 heures/année » figurant à l'art. 7 du contrat, consacré à la rémunération au forfait, n'a pas pour vocation d'arrêter la durée du travail hebdomadaire. Ils ont en outre déduit des conditions-cadre, édictées le 21 avril 1998, par le Gehval, au sujet des honoraires médicaux, que les médecins-chefs ne sont pas soumis à un horaire de travail, mais que la durée de leur activité varie d'un jour à l'autre en fonction des besoins. Ils ont à ce sujet arrêté que tous les médecins-chefs entendus en procédure effectuaient un horaire hebdomadaire de plus de 45 heures - en moyenne plus de 50 heures - sans avoir jamais fait valoir de prétention.
5.2 Après avoir recopié le passage critiqué du jugement entrepris, le recourant se contente d'affirmer que les considérations de l'autorité cantonale justifient que les médecins-chefs soient soumis à n'importe quelles conditions de travail, y compris les plus extrêmes, le seul critère digne de considération étant les besoins de l'institution hospitalière, avant d'ajouter qu'il a été établi que personne ne pouvait sortir indemne du rythme de travail qui lui avait été imposé. Force est de constater qu'en tenant de tels propos, le recourant ne démontre pas, d'une manière conforme à l'<ref-law>, en quoi l'autorité cantonale aurait violé l'<ref-law>. Le recourant ne tente même pas de prétendre qu'il aurait effectué des horaires allant au-delà de l'usage dans la profession, ce qu'il n'y a du reste pas lieu d'inférer, dès lors qu'il a été souverainement retenu que tous les médecins-chefs, y compris le recourant, effectuaient en moyenne plus de 50 heures par semaine.
Le recourant revient essentiellement sur le terme « 9 heures/année ». Il soutient que l'autorité cantonale a sombré dans l'arbitraire en ayant considéré que ce terme ne visait pas l'horaire de travail, mais une simple échelle de rémunération. Dans la mesure où cette considération relève de l'appréciation des preuves et du fait en découlant, le moyen est infondé, puisqu'aucune exception au sens de l'<ref-law> n'a été soulevée en lien avec le fait en question. Quoi qu'il en soit, le recourant ne démontre pas à satisfaction que l'autorité cantonale aurait fait montre d'arbitraire, puisqu'il se limite, d'une part, à retranscrire partiellement la déposition de D._ pour tenter de lui donner un sens différent de celui retenu par la cour et, d'autre part, à opposer sa propre appréciation à celle de la cour s'agissant du libellé de l'art. 7.
Le recourant prétend enfin que si la notion « 9 heures/année » ne devait pas signifier 45 heures de travail par semaine, le contrat de travail devrait être lu comme s'il comprenait une semaine de 45 h, soit le maximum légal selon l'art. 9 LTr. Dès lors qu'il a été jugé que la LTr ne trouvait pas application dans le cas d'espèce, le grief est infondé.
6. Au terme de cet examen, le recours ne peut qu'être rejeté dans la mesure de sa recevabilité.
7. Comme la valeur litigieuse, calculée selon les prétentions à l'ouverture de l'action (<ref-ruling> consid. 5b), dépasse le seuil de 30'000 fr., le montant de l'émolument judiciaire est fixé d'après le tarif ordinaire (<ref-law>) et non réduit (art. 65 al. 4 let. c LTF).
Compte tenu de l'issue du litige, le recourant, qui succombe, doit acquitter l'émolument judiciaire et les dépens à allouer à l'intimée (art. 66 al. 1 et 68 al. 1 et 2 LTF).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté dans la mesure où il est recevable.
2. Les frais judiciaires, arrêtés à 6'500 fr., sont mis à la charge du recourant.
3. Une indemnité de 7'500 fr., à payer à l'intimée à titre de dépens, est mise à la charge du recourant.
4. Le présent arrêt est communiqué en copie aux mandataires des parties et à la IIe Cour civile du Tribunal cantonal du canton du Valais.
Lausanne, le 17 décembre 2007 / CMF
Au nom de la Ire Cour de droit civil
du Tribunal fédéral suisse
Le Président: La Greffière:
Corboz Crittin