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.