Faits:
A. X._, ressortissant français né en 1974, a été condamné le 29 septembre 1999 à une peine de dix ans de réclusion, pour meurtre et délit manqué de meurtre. Le 5 avril 1998, mû par des sentiments de jalousie, de dépit et de désespoir, il avait en effet tiré deux coups de feu, avec un fusil de chasse, l'un sur son amie intime, qui venait de le quitter, l'autre sur le nouvel ami de celle-ci, provoquant la mort de la première et blessant grièvement le second.
X._ a bénéficié d'un régime de semi-liberté depuis le 1er avril 2003 et a été libéré conditionnellement dès le 4 décembre 2004. A l'occasion d'un congé, il a fait la connaissance de Y._, ressortissante suisse, qu'il a épousée le 4 juin 2004. Un fils, prénommé Z._, est issu de cette union, en 2005.
B. Le 15 juin 2004, X._ a sollicité l'octroi d'une autorisation de séjour CE/AELE de la part des autorités de police des étrangers valaisannes. Cette requête a été rejetée par le Service de l'état civil et des étrangers du canton du Valais (ci-après: le Service cantonal) le 19 novembre 2004. Au cours de la procédure de recours cantonale engagée par l'intéressé contre cette décision, le Service cantonal a accepté, le 24 janvier 2006, de reconsidérer sa décision initiale et a transmis le dossier pour approbation à l'Office fédéral des migrations (ci-après: l'Office fédéral).
Par décision du 25 avril 2006, l'Office fédéral a refusé de donner son approbation à l'octroi d'une autorisation de séjour et a prononcé le renvoi de Suisse de X._.
Saisi d'un recours dirigé contre la décision précitée de l'Office fédéral, le Tribunal administratif fédéral l'a rejeté, par arrêt du 6 novembre 2007. Il a retenu en substance que X._ avait commis un crime d'une extrême gravité en attentant à la vie d'autrui, soit au bien juridique le plus précieux. En dépit de l'évolution positive de l'intéressé depuis son incarcération, notamment de la réussite de son intégration socio-professionnelle, le profil de sa personnalité établi par l'expertise psychiatrique effectuée dans le cadre de la procédure pénale et la courte période écoulée depuis sa libération conditionnelle ne permettaient pas de considérer qu'il ne présentait plus actuellement une menace pour la sécurité et l'ordre publics et que l'on pouvait attendre de sa femme et de son fils qu'ils s'installent avec leur mari et père en France, la proximité de ce pays leur laissant la possibilité de maintenir des relations régulières avec les membres de leur famille établis en Valais.
C. Dans une écriture intitulée recours de droit public, X._ demande au Tribunal fédéral, sous suite de frais et dépens, préliminairement d'accorder l'effet suspensif à son recours, principalement, de réformer l'arrêt attaqué et d'approuver l'octroi de l'autorisation de séjour sollicitée, subsidiairement, d'annuler l'arrêt entrepris et de renvoyer l'affaire au Tribunal administratif fédéral ou à l'Office fédéral pour nouveau jugement ou nouvelle décision. Il se plaint d'une violation des règles sur le constat des faits et les preuves et invoque une violation de l'Accord du 1er juin 1999 entre la Confédération suisse, d'une part, et la Communauté européenne et ses Etats membres, d'autre part, sur la libre circulation des personnes (ci-après: ALCP ou l'Accord; RS 0.142.112.681), de l'art. 8 de la Convention du 4 novembre 1950 de sauvegarde des droits de l'homme et des libertés fondamentales (CEDH; RS 0.101) et de l'art. 36 al. 3 Cst.
Le Tribunal administratif fédéral renonce à se prononcer sur le recours. L'Office fédéral propose de le rejeter.
D. Par ordonnance du 11 décembre 2007, le Président de la IIe Cour de droit public du Tribunal fédéral a admis la demande d'effet suspensif présentée.

Considérant en droit:
1. Le Tribunal fédéral examine d'office et librement la recevabilité des recours qui lui sont soumis (art. 29 al. 1 de la loi du 17 juin 2005 sur le Tribunal fédéral [LTF; RS 173.110]; <ref-ruling> consid. 2 p. 188).
1.1 Bien que le recours ne porte pas une dénomination exacte, il faut admettre que le recourant entend agir par la voie du recours en matière de droit public au sens des <ref-law>, soit par celle indiquée au pied de l'arrêt attaqué.
1.2 D'après l'art. 83 lettre c ch. 2 LTF, le recours en matière de droit public est irrecevable contre les décisions en matière de droit des étrangers qui concernent une autorisation à laquelle ni le droit fédéral, ni le droit international, ne donnent droit. Il n'existe en principe pas de droit à l'octroi d'une autorisation de séjour ou d'établissement, à moins que l'étranger ou un membre de sa famille vivant en Suisse ne puisse invoquer dans ce sens une disposition particulière du droit fédéral ou d'un traité (<ref-ruling> consid. 1 p. 342 ss; <ref-ruling> consid. 2.1 p. 284 et les références citées).
1.2.1 La loi fédérale du 16 décembre 2005 sur les étrangers (LEtr; RS 142.20) est entrée en vigueur le 1er janvier 2008 (RO 2007 5487). En vertu de l'art. 126 al. 1 de cette loi, les demandes déposées avant son entrée en vigueur sont régies par l'ancien droit. Par conséquent, la présente cause doit être examinée, pour ce qui est du droit interne, sous l'angle de la loi fédérale du 26 mars 1931 sur le séjour et l'établissement des étrangers (LSEE; RS 1 p. 113).
1.2.2 En sa qualité de ressortissant français, le recourant peut, en principe, prétendre à l'octroi d'une autorisation de séjour, que ce soit au titre du regroupement familial ou pour exercer une activité lucrative en Suisse (cf. art. 4 et 7 ALCP et 2 § 1 et 3 de l'annexe I ALCP). Il échappe ainsi au motif d'irrecevabilité prévu par l'art. 83 lettre c ch. 2 LTF (cf., sous l'ancien droit, l'art. 100 al. 1 lettre b ch. 3 OJ; <ref-ruling> consid. 1.2 p. 343 et les arrêts cités). En outre, en tant que conjoint d'une ressortissante suisse, le recourant peut se prévaloir de l'art. 7 al. 1 (1ère phrase) LSEE pour obtenir une autorisation de séjour en Suisse. Dans la mesure où il forme une véritable union conjugale avec son épouse et qu'il entretient une relation étroite et effective avec son fils, de nationalité suisse, il peut également invoquer le droit à la protection de la vie familiale découlant de l'art. 8 § 1 CEDH (<ref-ruling> consid. 5 p. 269). Son recours est donc également recevable au regard de ces dispositions.
1.3 Au surplus, déposé en temps utile (<ref-law>) et dans les formes prescrites par la loi (<ref-law>) par le destinataire de la décision attaquée qui a un intérêt digne de protection à son annulation ou à sa modification (<ref-law>), le recours est recevable en vertu des <ref-law>.
2. 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; cf. Message du 28 février 2001 concernant la révision totale de l'organisation judiciaire fédérale, in FF 2001 4000, p. 4135) 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).
Pour le reste, le Tribunal fédéral applique d'office le droit fédéral (<ref-law>). Il n'est limité ni par les arguments des parties ni par la motivation retenue par l'autorité précédente; il peut ainsi admettre un recours pour un autre motif que ceux invoqués devant lui ou rejeter un recours en adoptant une argumentation différente de l'autorité attaquée (cf. <ref-ruling> consid. 1.4.1 p. 254; <ref-ruling> consid. 2.5 p. 262; <ref-ruling> consid. 1.4 p. 140).
3. 3.1 Selon l'art. 7 al. 1 LSEE, le droit du conjoint étranger d'un ressortissant suisse à l'octroi et à la prolongation d'une autorisation de séjour s'éteint lorsqu'il existe un motif d'expulsion. D'après l'art. 10 al. 1 LSEE, l'étranger peut être expulsé de Suisse ou d'un canton notamment s'il a été condamné par une autorité judiciaire pour crime ou délit (lettre a) ou si sa conduite, dans son ensemble, et ses actes permettent de conclure qu'il ne veut pas s'adapter à l'ordre établi dans le pays qui lui offre l'hospitalité ou qu'il n'en est pas capable (lettre b).
En l'espèce, il ne fait pas de doute que le motif d'expulsion figurant à l'art. 10 al. 1 lettre a LSEE est réalisé, puisque le recourant a été condamné à dix ans de réclusion pour meurtre et délit manqué de meurtre. Le refus d'octroyer ou de prolonger une autorisation de séjour sur la base de l'une des causes énoncées à l'art. 10 LSEE suppose toutefois une pesée des intérêts en présence ainsi que l'examen de la proportionnalité de la mesure (cf. art. 11 al. 3 LSEE; cf. <ref-ruling> consid. 3.3.4 p. 182; <ref-ruling> consid. 4a p. 12 ss). Pour apprécier ce qui est équitable, l'autorité tiendra notamment compte de la gravité de la faute commise par l'étranger, de la durée de son séjour en Suisse et du préjudice qu'il aurait à subir avec sa famille du fait de l'expulsion, respectivement du refus d'accorder ou de prolonger une autorisation de séjour (cf. art. 16 al. 3 RSEE).
3.2 Par ailleurs, en vertu de l'art. 5 al. 1 de l'annexe I ALCP, le refus d'accorder ou de renouveler une autorisation de séjour à un ressortissant d'une partie contractante à l'Accord ou à un membre de sa famille ne peut se fonder que sur des motifs d'ordre public, de sécurité publique et de santé publique.
Conformément à la jurisprudence de la Cour de justice des Communautés européennes (ci-après: la Cour de justice ou CJCE), les limites posées au principe de la libre circulation des personnes doivent s'interpréter de manière restrictive. Ainsi, le recours par une autorité nationale à la notion de l'ordre public pour restreindre cette liberté suppose, en dehors du trouble de l'ordre social que constitue toute infraction à la loi, l'existence d'une menace réelle et d'une certaine gravité affectant un intérêt fondamental de la société (cf. <ref-ruling> consid. 3.4.1 p. 182; <ref-ruling> consid. 7.3 p. 222 et les arrêts cités de la CJCE du 27 octobre 1977, Bouchereau, 30/77, Rec. 1977, p. 1999, points 33-35; du 19 janvier 1999, Calfa, C-348/96, Rec. 1999, p. I-11, points 23 et 25). En outre, les mesures d'ordre public ou de sécurité publique doivent être fondées, aux termes de l'art. 3 § 1 de la directive 64/221/CEE, exclusivement sur le comportement personnel de celui qui en fait l'objet. Des motifs de prévention générale détachés du cas individuel ne sauraient donc les justifier (<ref-ruling> consid. 3.4.1 p. 183; <ref-ruling> consid. 7.1 p. 221 et l'arrêt cité de la CJCE du 26 février 1975, Bonsignore, 67/74, Rec. 1975, p. 297, points 6 et 7). D'après l'art. 3 § 2 de la directive 64/221/CEE, la seule existence de condamnations pénales (antérieures) ne peut automatiquement motiver de telles mesures. Les autorités nationales sont tenues de procéder à une appréciation spécifique, portée sous l'angle des intérêts inhérents à la sauvegarde de l'ordre public, qui ne coïncide pas nécessairement avec les appréciations à l'origine des condamnations pénales. Autrement dit, ces dernières ne peuvent être prises en considération que si les circonstances les entourant laissent apparaître l'existence d'une menace actuelle pour l'ordre public (<ref-ruling> consid. 3.4.1 p. 183; <ref-ruling> consid. 7.4 p. 222). Selon les circonstances, la Cour de justice admet néanmoins que le seul fait du comportement passé de la personne concernée puisse réunir les conditions de pareille menace actuelle (<ref-ruling> consid. 3.4.1 p. 183 ss et l'arrêt précité de la CJCE Bouchereau, point 29). Celles-ci ne supposent en tout cas pas qu'il soit établi avec certitude que l'étranger commettra d'autres infractions à l'avenir; inversement, ce serait aller trop loin que d'exiger que le risque de récidive soit nul pour que l'on renonce à une mesure d'ordre public. En réalité, ce risque doit s'apprécier en fonction de l'ensemble des circonstances du cas et, en particulier, de la nature et de l'importance du bien juridique menacé ainsi que de la gravité de l'atteinte potentielle qui pourrait y être portée; il faudra se montrer d'autant plus rigoureux dans cet examen que le bien juridique menacé est important (cf. <ref-ruling>, consid. 3.3 p. 499 ss, 176 consid. 4.3.1 p. 185 ss).
4. 4.1 Le recourant reproche au Tribunal administratif fédéral de s'être fondé à tort sur une expertise psychiatrique ancienne pour définir le profil de sa personnalité, sans tenir compte de la longue évolution qui avait été la sienne, telle qu'elle a été décrite par les professionnels qualifiés qui l'ont suivi tout au long des étapes de son incarcération. En outre, en retenant à sa charge la courte période écoulée depuis sa libération conditionnelle, le Tribunal administratif fédéral aurait omis de tenir compte des cinq années de détention antérieures au cours desquelles les autorités pénitentiaires avaient eu à plusieurs reprises l'occasion de porter une appréciation favorable sur l'évolution de son caractère. En se focalisant sur la gravité des faits ayant entraîné sa condamnation pénale en 1999, sur les circonstances du meurtre commis en 1998 et sur le profil de sa personnalité mis en évidence il y a plus de neuf ans pour en conclure qu'un risque de récidive ne pouvait pas être écarté, l'autorité intimée aurait violé l'art. 5 al. 1 de l'annexe I ALCP et la Directive 64/221/CEE exigeant que le danger social découlant de la présence d'un étranger soit apprécié au moment même où la décision d'éloignement est prise à son égard.
4.2 Le cas d'espèce a ceci de particulier que le recourant s'est rendu coupable d'un acte intrinsèquement très grave, imposant le respect d'importantes précautions au plan de la sauvegarde de l'ordre et de la sécurité publics, et qu'il a fait preuve, depuis l'assouplissement de ses conditions de détention, d'une évolution socio-professionnelle en tous points remarquable. En 1998, le recourant était décrit comme un homme désorienté et aveuglé par un amour maladif. Sa jalousie, qui l'avait amené à menacer et frapper son amie, avait instauré un contexte relationnel extrêmement tendu. Le passage à l'acte avait été consécutif au caractère possessif de l'intéressé et à son esprit de vengeance égoïste. Près de dix ans plus tard, le recourant est un homme marié et père d'un jeune enfant, comblé affectivement, établi au sein d'une communauté villageoise où il a été accueilli chaleureusement, tant par sa belle-famille que par les habitants, et auquel son employeur a confié des responsabilités dans l'exercice desquelles il est apprécié, tant de ses supérieurs que de ses subordonnés.
L'expertise psychiatrique de 1998, sur laquelle l'autorité intimée se fonde pour affirmer qu'un risque de récidive ne peut pas être exclu, relevait que le recourant souffrait de certains troubles du développement psycho-affectif; sa personnalité présentait des traits anxieux et dépendants ainsi qu'une labilité émotionnelle de type impulsif. L'expert soulignait la faible tolérance à la frustration et à l'isolement, ainsi qu'un manque de recul pour mesurer la portée de ses actes en situation de "stress". Certes, l'expert indiquait que le recourant ne présentait pas de danger pour autrui et ne compromettait pas la sécurité publique. Cette affirmation doit toutefois être comprise dans ce sens que l'absence de danger résultait du fait que le recourant ne se trouvait plus en situation d'abandon affectif. De même que le comportement criminel du recourant en 1998 était exclusivement lié à la rupture de sa liaison sentimentale, le risque de récidive actuel est-il limité à la question de savoir si le recourant serait aujourd'hui en mesure de surmonter une nouvelle déception amoureuse. Le souci de la protection de l'ordre et de la sécurité publics concerne donc avant tout la famille proche et l'entourage de l'intéressé. L'autorité de police des étrangers doit en conséquence déterminer si la personnalité du recourant, caractérisée en 1998 par des traits anxieux et dépendants entraînant une intolérance à la frustration et à l'isolement, a suffisamment évolué pour admettre qu'aujourd'hui, placé dans des circonstances analogues à la rupture sentimentale vécue en 1998, le recourant serait capable de maîtriser ses pulsions et de dominer ses sentiments de jalousie, de dépit et de désespoir. Le degré de certitude quant à l'évolution positive du recourant doit être d'autant plus élevé que le risque à prendre en considération est important puisque le recourant n'a pu surmonter ses frustrations qu'en éliminant physiquement la personne qui en était la cause. Et il paraît évident que le recourant s'est en tout cas autant investi dans la relation amoureuse qui le lie à sa femme que dans celle qu'il avait nouée avec son amie de jeunesse.
L'existence d'un risque actuel de réitération d'actes aussi graves que l'atteinte à la vie d'autrui ne saurait être admise à l'aune des constats et des conclusions de la seule expertise psychiatrique mise en oeuvre par les autorités pénales jurassiennes en 1998 dans la mesure où cette expertise ne prend évidemment pas en compte le chemin parcouru par le recourant depuis près de dix ans et les incidences des expériences vécues sur la structure de sa personnalité. A l'inverse, l'affirmation qu'un tel risque est exclu ne peut pas trouver son fondement dans les rapports des différents organes pénitentiaires cités par le recourant. Certes, ces rapports font état d'une ouverture du recourant à la discussion, de la perception de la relation amoureuse sous un angle moins possessif, d'une prise de conscience de la gravité des actes commis, de l'acquisition d'une certaine maturité et des réflexions auxquelles le recourant a pu se livrer sur ses réactions, ses besoins, ses limites et son mode relationnel. Sans mettre en doute la sincérité et la compétence des auteurs de ces rapports - geôliers, directeurs d'établissement pénitentiaire et assistants sociaux - il faut constater que ces professionnels du milieu carcéral ne disposent pas de toutes les connaissances spécifiques nécessaires à l'évaluation pointue de l'évolution de la personnalité et que leurs appréciations, portées à différents moments du parcours de détenu du recourant, sont insuffisantes pour se prononcer sur l'aspect actuel du risque de récidive alors que le recourant n'est plus incarcéré. Dans ces conditions, la garantie que le drame du 5 avril 1998 ne constituait qu'un "accident de parcours" et que le risque de réitération puisse être raisonnablement exclu nécessite la mise en oeuvre d'une nouvelle expertise psychiatrique ou psychologique destinée à cerner l'ampleur de l'évolution personnelle du recourant et à poser un diagnostic répondant aux exigences d'actualité du risque de récidive. Pour le cas où une telle garantie serait établie, rien ne s'opposerait à l'octroi de l'autorisation de séjour sollicitée par le recourant.
Il se justifie dès lors de renvoyer l'affaire à l'autorité intimée afin qu'elle fasse procéder aux investigations complémentaires mentionnées ci-dessus. Il est donc superflu d'examiner, en l'état, les griefs du recourant liés à la pesée des intérêts publics et privés et au respect du principe de la proportionnalité au sens des art. 8 CEDH et 36 al. 3 Cst.
5. Vu ce qui précède, il y a lieu d'admettre le recours, d'annuler l'arrêt attaqué et de renvoyer la cause au Tribunal administratif fédéral pour nouvelle décision dans le sens des considérants.
Bien qu'elle succombe, la Confédération, dont l'intérêt patrimonial n'est pas en cause, n'a pas à supporter de frais judiciaires (art. 66 al. 1 et 4 LTF).
Obtenant gain de cause, le recourant a droit à des dépens pour la procédure devant le Tribunal fédéral et devant le Tribunal administratif fédéral (art. 68 al. 1 et 5 LTF).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est admis et l'arrêt rendu le 6 novembre 2007 par le Tribunal administratif fédéral est annulé.
2. L'affaire est renvoyée pour nouvelle décision dans le sens des considérants au Tribunal administratif fédéral.
3. Il n'est pas perçu de frais judiciaires.
4. Une indemnité de 3'000 fr., à payer au recourant à titre de dépens pour la procédure devant le Tribunal fédéral et le Tribunal administratif fédéral, est mise à la charge de la Confédération.
5. Le présent arrêt est communiqué au mandataire du recourant, au Tribunal administratif fédéral, à l'Office fédéral des migrations, ainsi qu'au Service de l'état civil et des étrangers du canton du Valais.
Lausanne, le 10 mars 2008
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: La Greffière:
T. Merkli E. Kurtoglu-Jolidon