Faits:
A. X._, ressortissant turc né le *** 1964, serait arrivé en Suisse en 1987 et reparti en 1991, après que sa demande d'asile aurait été rejetée. Il est revenu en Suisse en février 2002, où il a alors séjourné et travaillé illégalement, avant de se voir notifier, le 27 septembre 2002, une décision de renvoi, ainsi qu'une décision d'interdiction d'entrée.
Le 29 octobre 2003, X._ a épousé A._, née le *** 1959, divorcée et mère de trois enfants. A._ est originaire de Macédoine et détentrice d'une autorisation d'établissement. A la suite de ce mariage, l'Office fédéral des migrations a annulé la mesure d'interdiction d'entrée et, par décision du 9 août 2004, X._ a obtenu une autorisation de séjour. X._ et A._ se sont séparés de janvier 2005 à janvier 2006, ainsi que trois semaines en août 2007. Le 4 décembre 2008, le Service des migrations du canton de Neuchâtel (ci-après: le Service des migrations) a délivré à X._ une autorisation d'établissement valable depuis le 29 octobre 2008.
Le 19 janvier 2009, X._ a définitivement quitté le domicile conjugal.
Après qu'un jugement du 3 avril 2009 d'un tribunal turc lui eut octroyé la garde de ses deux fils vivant en Turquie, B._ et C._, nés respectivement le *** 1994 et le *** 2001, X._ a déposé, le 6 avril 2009, une demande d'autorisation de séjour en vue d'un regroupement familial.
Le 6 mai 2009, les époux X._-A._ ont présenté une requête commune de divorce, lequel a été prononcé le 27 octobre 2009.
Par décision du 13 janvier 2010, le Service des migrations a révoqué l'autorisation d'établissement de X._, considérant qu'au moment de l'octroi de celle-ci, la communauté conjugale n'existait plus que formellement et que l'intéressé, en invoquant ce mariage, commettait un abus de droit. Le Département de l'économie du canton de Neuchâtel (ci-après: le Département de l'économie) a rejeté le recours de X._, le 11 mars 2011, pour la même raison.
B. Par arrêt du 15 août 2011, la Cour de droit public du Tribunal cantonal du canton de Neuchâtel (ci-après: le Tribunal cantonal) a également rejeté le recours de X._. Il a, en substance, jugé que l'enchaînement chronologique particulièrement rapide entre l'obtention de l'autorisation d'établissement, la séparation définitive et la demande de regroupement familial pour les enfants de X._ était "de nature à fonder la présomption" que l'intéressé avait choisi d'épouser une personne titulaire d'une autorisation d'établissement dans le but de s'installer en Suisse et d'obtenir un droit de séjour assuré afin d'y faire venir ses enfants. En procédant ainsi, X._ avait manifestement trompé le Service des migrations. Dès lors, la révocation de l'autorisation était justifiée. En outre, l'intéressé ne représentait pas un cas d'extrême gravité permettant de déroger aux conditions d'admission.
C. Agissant par la voie du recours en matière de droit public, X._ demande au Tribunal fédéral, sous suite de frais et dépens, d'annuler l'arrêt du 15 août 2011 du Tribunal cantonal, ainsi que de dire et constater qu'il a droit au maintien de son autorisation d'établissement, subsidiairement, de dire et constater qu'il se trouve dans une situation d'extrême gravité et de lui accorder une autorisation de séjour.
Le Service des migrations, le Tribunal cantonal et l'Office fédéral des migrations concluent au rejet du recours. Les observations du Département de l'économie sont tardives.

Considérant en droit:
1. 1.1 Selon l'art. 83 let. c LTF, le recours en matière de droit public est irrecevable à l'encontre des 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 (ch. 2) ou qui concernent des dérogations aux conditions d'admission (ch. 5).
1.2 Le recourant est titulaire d'un permis d'établissement qui, sans la révocation litigieuse, continuerait à déployer ses effets. En ce sens, il peut se prévaloir d'un droit au maintien de cette autorisation au sens de l'art. 83 let. c ch. 2 LTF et son recours échappe au motif d'irrecevabilité prévu par cette disposition (cf. <ref-ruling> consid. 1.2.1 p. 4).
Pour le surplus, le recours est recevable au regard des art. 42 et 82 ss LTF.
1.3 Toutefois, la présente procédure a partiellement pour origine le refus des autorités précédentes de mettre le recourant au bénéfice de l'art. 30 al. 1 let. b LEtr et de déroger aux conditions d'admission dans le but de tenir compte d'un cas "d'une extrême gravité" (permis dit humanitaire). En raison de la nature potestative de cette disposition ("Kann-Vorschrift"), le recourant ne peut en déduire aucun droit (<ref-ruling> consid. 3.2.1 p. 348). En outre, comme refus de déroger aux conditions d'admission, l'arrêt attaqué ne peut de toute façon pas faire l'objet d'un recours en matière de droit public en vertu de l'art. 83 let. c ch. 5 LTF. Partant, le recours est irrecevable en tant qu'il est fondé sur l'art. 30 al. 1 let. b LEtr.
2. Saisi d'un recours en matière de droit public, le Tribunal fédéral examine en principe librement la violation du droit fédéral (cf. art. 95 let. a et 106 al. 1 et 2 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 ceux-ci n'aient été établis de façon manifestement inexacte - ce qui correspond à la notion d'arbitraire (<ref-ruling> consid. 4.3 p. 63) - ou en violation du droit au sens de l'<ref-law> (cf. <ref-law>).
3. Le Tribunal cantonal a retenu, comme motif de révocation, la présomption que le recourant avait épousé une personne titulaire d'une autorisation d'établissement dans le but prépondérant de s'installer en Suisse et non de former une véritable union conjugale. Il convient donc d'examiner si tel est le cas et si le recourant a alors caché cet élément aux autorités pour obtenir ladite autorisation.
3. Le Tribunal cantonal a retenu, comme motif de révocation, la présomption que le recourant avait épousé une personne titulaire d'une autorisation d'établissement dans le but prépondérant de s'installer en Suisse et non de former une véritable union conjugale. Il convient donc d'examiner si tel est le cas et si le recourant a alors caché cet élément aux autorités pour obtenir ladite autorisation.
3.1 3.1.1 D'après l'art. 63 al. 1 let. a LEtr (en lien avec l'art. 62 let. a LEtr), l'autorité compétente peut révoquer une autorisation d'établissement lorsque l'étranger ou son représentant légal a fait de fausses déclarations ou a dissimulé des faits essentiels durant la procédure d'autorisation. Sont décisifs, selon la jurisprudence, non seulement les faits sur lesquels l'autorité a expressément demandé des précisions, mais, suivant les faits, également ceux dont le recourant devait savoir qu'ils étaient déterminants pour l'octroi du permis (<ref-ruling> consid. 4.1 p. 9 relatif à l'ancien droit; jurisprudence reprise sous le nouveau droit: arrêt 2C_15/2011 du 31 mai 2011 consid. 4.2.1 et les références citées). Le silence ou l'information erronée doivent avoir été utilisés de manière intentionnelle, à savoir dans l'optique d'obtenir l'autorisation litigieuse (cf. arrêts 2C_811/2010 du 23 février 2011 et les arrêts cités). L'étranger est tenu d'informer l'autorité de manière complète et conforme à la vérité sur tous les faits déterminants pour l'octroi de l'autorisation; il doit en particulier indiquer si la communauté conjugale n'est plus effectivement vécue (arrêt 2C_15/2011 du 31 mai 2011 consid. 4.2.1). Il y a dissimulation lorsque l'étranger expose les raisons de sa demande aux autorités de manière à provoquer, respectivement à maintenir, une fausse apparence sur un fait essentiel. Cependant, pour qu'il y ait tromperie de la part de l'étranger, il faut que l'autorité compétente établisse les faits déterminants pour l'obtention de l'autorisation en posant les questions pertinentes pour ce faire (<ref-ruling> consid. 3 p. 99; arrêts 2C_211/2012 du 3 août 2012 consid. 3.1; 2C_595/2011 du 24 janvier 2012 consid. 3.4; 2C_403/2011 du 2 décembre 2011 consid. 3.3.3). Si tel n'a pas été le cas, la personne concernée ne peut pas se voir reprocher facilement d'avoir obtenu l'autorisation grâce à de fausses déclarations ou la dissimulation de faits essentiels (ANDREAS ZÜND/LADINA ARQUINT HILL, Beendigung der Anwesenheit, Entfernung und Fernhaltung, in: Uebersax/Rudin/Hugi Yar/Geiser [éd.], Ausländerrecht, 2e éd., 2009, no 8.27 p. 324).
Au demeurant, le refus de l'autorisation ou la révocation de celle-ci ne se justifie que si la pesée des intérêts à effectuer dans le cas d'espèce fait apparaître la mesure comme proportionnée aux circonstances. Il convient donc de prendre en considération les intérêts publics, la situation personnelle de l'étranger, ainsi que son degré d'intégration (cf. art. 96 al. 1 LEtr; <ref-ruling> consid. 4.3 p. 381).
3.1.2 L'étranger fait preuve d'un comportement trompeur s'il a, dans la procédure d'octroi d'autorisation d'établissement, sciemment tu ou activement caché que pendant la période de cinq ans, déterminante pour l'acquisition de cette autorisation, l'union matrimoniale était vouée à l'échec. La jurisprudence relative à l'invocation abusive de l'union matrimoniale est, ici, pertinente même si elle n'a qu'une portée indirecte (<ref-ruling> consid. 4.2 p. 9). Selon cette jurisprudence, est considérée comme abusive l'invocation d'un mariage qui n'a plus de substance et n'existe plus que formellement parce que l'union conjugale apparaît définitivement rompue, faute de chances de réconciliation entre les époux (cf. <ref-ruling> consid. 4.2 p. 117; <ref-ruling> consid. 2 et 3 p. 151 s.). Dans cette hypothèse, l'intention réelle des époux ne peut souvent pas être établie par une preuve directe, mais seulement grâce à des indices (cf. <ref-ruling> consid. 5a p. 57 rendu sous l'ancien droit; arrêt 2C_811/2010 du 23 février 2011 consid. 4.4.1 pour le nouveau droit); l'état de fait amenant à qualifier l'invocation de l'union matrimoniale comme abusive ne peut pas être retenu à la légère (<ref-ruling> consid. 4.2 p. 9).
3.2 Selon les constatations cantonales, le recourant est revenu en Suisse en février 2002 et y a alors séjourné et travaillé illégalement, avant de faire l'objet d'une décision de renvoi et d'une interdiction d'entrée prononcées en septembre 2002. L'arrêt cantonal ne dit rien sur le moment et les circonstances de la rencontre entre les deux intéressés, le recourant alléguant qu'il a rencontré A._ "courant de l'année 2002" dans un établissement public. On sait par contre que, le 29 octobre 2003, il se mariait avec A._, de cinq ans son aînée et qui avait trois enfants; le recourant en avait deux qui vivaient avec leur mère en Turquie. Le Service des migrations lui a alors octroyé, en date du 9 août 2004, une autorisation de séjour.
Il ressort encore de l'arrêt attaqué que, après quatorze mois de communauté conjugale, soit en janvier 2005, les époux se sont séparés pendant une année; puis, après avoir repris la vie commune en janvier 2006, ils ont de nouveau vécu séparément trois semaines en août 2007. Le 4 décembre 2008, le Service des migrations a octroyé une autorisation d'établissement, valable depuis le 29 octobre 2008, au recourant. Les époux se sont définitivement quittés le 19 janvier 2009. Puis, après qu'un tribunal turc lui eut accordé, le 3 avril 2009, la garde de ses enfants, le recourant a requis, le 6 avril suivant, le regroupement familial. Les époux ont déposé le 6 mai 2009 une demande commune en divorce. Le 13 juillet 2009, l'autorité a signifié au recourant qu'elle entendait révoquer son autorisation d'établissement.
3.3 Il s'agit de déterminer si le recourant a eu un comportement trompeur avant le 29 octobre 2008. Or, le dossier n'apporte pas d'indications sur les informations que le recourant a fournies avant l'octroi de l'autorisation d'établissement, ni sur les éventuelles questions que l'autorité compétente lui aurait posées et les réponses y relatives. Aucun élément ne permet de penser que le recourant aurait donné de faux renseignements ou tu sciemment des faits. Il ressort des pièces que le recourant n'a jamais caché que les époux s'étaient séparés de janvier 2005 à janvier 2006, puis quelques jours en 2007; les autorités savaient donc que le couple rencontrait des difficultés. L'union conjugale était effectivement vécue puisqu'un certificat médical du 5 décembre 2003 atteste que A._, qui était traitée pour un trouble dépressif, avait "fait la connaissance, il y a deux ans, d'un homme originaire de sa région; depuis lors, le soussigné a assisté à un épanouissement dans son rôle de femme et de mère et même à une amélioration de son état psychique. La patiente vient de se remarier en octobre dernier, aboutissement réfléchi de l'excellente entente du couple". L'intéressé n'a pas non plus dissimulé qu'il avait deux enfants, restés avec sa compagne d'alors en Turquie; le dossier comporte même une note manuscrite du recourant, datée du 11 mai 2004, déclarant "Pour l'instant je ne souhaite pas ramener mes enfants, on verra plus tard". Finalement, il faut relever que le recourant n'a pas demandé qu'une autorisation d'établissement lui soit octroyée: c'est, en effet, son employeur qui a requis, en remplissant le formulaire "Demande de main d'oeuvre étrangère" en octobre 2008, le renouvellement de l'autorisation de séjour; le 27 novembre suivant, le Service des migrations a fait savoir à l'intéressé qu'il pouvait prétendre à l'octroi d'une autorisation d'établissement; il lui demandait uniquement, à cette fin, une photocopie du passeport. Il semble que l'autorité n'a alors pas vérifié la situation de recourant. Le seul fait que les époux se sont séparés le 19 janvier 2009 ne suffit pas à prouver que l'union matrimoniale était déjà vouée à l'échec à la fin octobre 2008 et que le recourant a sciemment caché ce fait ou trompé l'autorité à ce sujet; en effet, celui-ci prétend que la détérioration de l'état psychique de son épouse en janvier 2009 et des difficultés avec le fils de celle-ci seraient à l'origine de leur rupture. Le Tribunal cantonal ne dit rien à ce sujet.
3.4 Le Tribunal fédéral ne dispose pas des éléments nécessaires pour corriger ou compléter d'office l'état de fait en application de l'<ref-law>, notamment quant aux renseignements demandés, le cas échéant, par l'autorité compétente avant d'octroyer l'autorisation d'établissement, aux éléments avancés par le recourant quant à la détérioration de l'état de son épouse début 2009 et aux problèmes rencontrés avec le fils de celle-ci. En conséquence, le Tribunal de céans ne peut pas juger si les conditions de l'art. 63 al. 1 let. a LEtr (en lien avec l'art. 62 let. a LEtr) sont remplies. La cause doit, dès lors, être renvoyée au Tribunal cantonal, afin qu'il complète les faits et rende une nouvelle décision.
4. Le recours doit ainsi être admis dans la mesure où il est recevable, l'arrêt attaqué annulé et la cause renvoyée au Tribunal cantonal pour une nouvelle décision dans le sens des considérants (<ref-law>).
Compte tenu de l'issue du litige, il ne sera pas perçu de frais judiciaires (cf. art. 66 al. 1 et 4 LTF). Le canton de Neuchâtel versera des dépens au recourant (cf. <ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est admis dans la mesure où il est recevable. L'arrêt attaqué est annulé. La cause est renvoyée au Tribunal cantonal pour une nouvelle décision dans le sens des considérants.
2. Il n'est pas perçu de frais judiciaires.
3. Le canton de Neuchâtel versera au recourant la somme de 2'000 fr. à titre de dépens pour la procédure devant le Tribunal fédéral.
4. Le présent arrêt est communiqué au mandataire du recourant, au Département de l'économie, au Service des migrations et au Tribunal cantonal de la République et canton de Neuchâtel, Cour de droit public, ainsi qu'à l'Office fédéral des migrations.
Lausanne, le 20 août 2012
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: Zünd
La Greffière: Kurtoglu-Jolidon