Faits: A. Après un séjour irrégulier en Suisse dès 1990, X._, ressortissant de l'ex-Yougoslavie, né en 1961, a épousé le 12 février 1991 Y._, ressortissante suisse, née en 1945. Il a, de ce fait, obtenu une autorisation de séjour, régulièrement renouvelée jusqu'à l'obtention du permis d'établissement, en date du 21 mars 1996. Le 28 mai 1996, l'intéressé a obtenu la nationalité suisse par naturalisation facilitée en qualité de conjoint d'un ressortissant suisse sur la base de l'art. 27 de la loi fédérale du 29 septembre 1952 sur l'acquisition et la perte de la nationalité suisse (LN; RS 141.0). Depuis le début de son mariage, X._ a entretenu, au Kosovo, une liaison régulière avec une compatriote, A._, née en 1964, avec laquelle il a eu six enfants: B._, né en 1991, C._, née en 1993, D._, née en 1995, E._, née en 1998, F._, né en 2000 et G._, né en 2006, qui ont toujours vécu avec leur mère au Kosovo. Le 8 janvier 1999, X._, d'entente avec son épouse, a déposé en vain auprès de l'Office fédéral des réfugiés une demande de visa pour inviter en Suisse dix-neuf personnes de sa famille, dont sa compagne et ses quatre premiers enfants, qu'il a désignés comme sa belle-soeur et ses neveux et nièces. Le couple X.Y._ s'est séparé à une date indéterminée, l'épouse ayant quitté le canton du Valais. Le divorce a été prononcé le 20 octobre 2005. Le 17 mai 2006, X._ a épousé, au Kosovo, A._. Le lendemain, celle-ci a déposé une demande d'entrée et de séjour en Suisse pour rejoindre son mari et vivre auprès de lui avec leurs cinq enfants. B. Par décision du 25 octobre 2007, le Service de l'état civil et des étrangers (actuellement le Service de la population et des migrations) du canton du Valais (ci-après: le Service cantonal) a rejeté la demande présentée par A.X._, B.X._, C.X._ et D.X._, celle des trois enfants cadets étant sans objet du fait de leur nationalité suisse. Ceux-ci étaient en effet nés après la naturalisation de leur père et, comme lui, avaient pu conserver leur nationalité en raison de l'écoule- ment du délai péremptoire de cinq ans de l'art. 41 LN permettant de faire annuler ces naturalisations. Le Service cantonal a considéré que X._ avait obtenu la naturalisation facilitée de manière frauduleuse, en dissimulant sa double vie et l'existence de ses enfants; son parcours démontrait que le but de son mariage avec une ressortissante suisse en 1991 était de lui permettre, à moyen terme, de s'assurer un statut en Suisse afin de se faire rejoindre ultérieurement par sa famille. Le 7 janvier 2009, le Conseil d'Etat du canton du Valais (ci-après: le Conseil d'Etat) a rejeté le recours déposé le 26 novembre 2007 par X._ contre la décision du Service cantonal du 25 octobre 2007. C. Saisi d'un recours dirigé contre la décision rendue le 7 janvier 2009 par le Conseil d'Etat, le Tribunal cantonal du canton du Valais, Cour de droit public (ci-après: le Tribunal cantonal), l'a rejeté, par arrêt du 29 mai 2009. Il a retenu, en substance, que X._ ne pouvait pas, sans commettre un abus de droit, se prévaloir de sa nationalité suisse pour obtenir le regroupement familial en faveur de son épouse actuelle et de ses enfants, que le droit du conjoint étranger d'un ressortissant suisse d'obtenir, au sens de l'art. 7 de la loi fédérale du 26 mars 1931 sur le séjour et l'établissement des étrangers (LSEE), une autorisation de séjour, puis, après cinq ans, une autorisation d'établissement, ne constituait pas un droit absolu mais trouvait sa limite dans l'interdiction de l'abus de droit, que s'il n'avait pas caché la relation qu'il entretenait parallèlement à son mariage avec une compatriote et l'existence de ses enfants, X._ n'aurait obtenu ni une autorisation de séjour, ni une autorisation d'établissement, ni la nationalité suisse, et que l'intéressé ne pouvait pas invoquer les art. 17 al. 2 LSEE et 8 de la Convention européenne de sauvegarde des droits de l'homme et des libertés fondamentales du 4 novembre 1950 (CEDH; RS 0.101), compte tenu de l'âge de ses trois aînés, de leur méconnaissance de la langue française et de leurs importantes difficultés prévisibles d'adaptation et d'intégration en Suisse. D. Par mémoire du 29 juin 2009, X._ demande au Tribunal fédéral de reconsidérer l'arrêt du Tribunal cantonal du 29 mai 2009, la décision du Conseil d'Etat du 12 janvier 2009, la décision du Service cantonal du 25 octobre 2007 et de donner un avis favorable relatif à l'entrée et au séjour en Suisse de son épouse et de ses enfants B._, C._ et D._. Il se plaint de la violation des art. 7 LSEE, 17 al. 2 LSEE et 8 CEDH. Le Tribunal cantonal renonce à se déterminer. Le Conseil d'Etat se réfère à l'arrêt attaqué et conclut, sous suite de frais, au rejet du recours dans la mesure de sa recevabilité. L'Office fédéral des migrations conclut au rejet du recours dans la mesure où il est recevable. 