Faits:
A. X._, ressortissant Turc, né en 1963, est venu une première fois en Suisse comme requérant d'asile en 1986. Sa demande ayant été rejetée, une interdiction d'entrée lui a été signifiée jusqu'en 1990. Revenu illégalement en Suisse en 1996, il a épousé, le 2 avril 2001, à Neuchâtel, Y._, ressortissante suisse, née en 1945 en Tunisie, et a obtenu une autorisation annuelle de séjour, renouvelée jusqu'au 2 avril 2006.
Le 28 janvier 2004, le Service des migrations du canton de Neuchâtel a rejeté la demande de regroupement familial présentée par X._ en faveur de ses deux filles restées en Turquie. Il a ensuite procédé à des investigations pour savoir si l'intéressé vivait régulièrement au domicile conjugal. Lors de son audition du 6 juillet 2006, X._ a déclaré être définitivement séparé de son épouse, suite à des problèmes conjugaux.
Par décision du 6 juillet 2007, le Service des migrations a refusé à X._ l'octroi d'une autorisation d'établissement, ainsi que la prolongation de son autorisation annuelle de séjour. Il a retenu en bref que les époux s'étaient séparés à plusieurs reprises depuis 2001, et définitivement depuis le 15 octobre 2005, soit avant l'échéance du délai de cinq ans permettant l'octroi d'une autorisation d'établissement. Ce prononcé a été confirmé, sur recours, par décision du Département de l'économie publique du 7 août 2008.
B. X._ a recouru contre la décision du Département de l'économie auprès du Tribunal administratif du canton de Neuchâtel, en alléguant qu'au mois de mai 2008, les époux avaient renoncé à divorcer et avaient envisagé de reprendre la vie commune.
Par arrêt du 19 janvier 2008, le Tribunal administratif a rejeté le recours. Il a jugé que le recourant commettait un abus de droit en invoquant un mariage qui n'existait plus que formellement déjà avant le délai de cinq ans et que la renonciation de l'épouse à la procédure de divorce ne suffisait pas pour admettre un espoir de réconciliation.
C. X._ forme un recours en matière de droit public auprès du Tribunal fédéral et conclut, avec suite de frais, à l'annulation de l'arrêt du Tribunal administratif du 19 janvier 2009. Il demande, principalement, l'octroi d'une autorisation d'établissement ou le renouvellement de son autorisation de séjour et, subsidiairement, le renvoi de l'affaire à l'autorité cantonale compétente pour qu'elle accorde les autorisations requises.
Le Tribunal administratif se réfère à son arrêt et conclut au rejet du recours. Le Département de l'économie conclut au rejet du recours, dans la mesure où il est recevable, avec suite de frais. L'Office fédéral des migrations propose de rejeter le recours.
D. Par ordonnance du Tribunal fédéral du 3 mars 2009, la demande d'effet suspensif présentée par le recourant a été admise.

Considérant en droit:
1. Le litige porte sur le droit du recourant d'obtenir le renouvellement de son autorisation de séjour ou une autorisation d'établissement. La demande ayant été déposée avant l'entrée en vigueur, le 1er janvier 2008, de la loi fédérale sur les étrangers du 16 décembre 2005 (LEtr; RS 142.20), le cas demeure régi par l'ancien droit (cf. art. 126 al. 1 LEtr), à savoir la loi fédérale du 26 mars 1931 sur le séjour et l'établissement des étrangers (LSEE; RS 1 113).
2. Le Tribunal fédéral examine d'office sa compétence et la recevabilité des recours qui lui sont soumis (cf. <ref-law>; <ref-ruling> consid. 1 p. 24; <ref-ruling> consid. 1.1 p. 3).
2.1 Aux termes de l'art. 83 let. c ch. 2 LTF, le recours en matière de droit public est irrecevable contre les décisions relatives à une autorisation de droit des étrangers à laquelle ni le droit fédéral ni le droit international ne donnent droit.
D'après l'art. 7 al. 1 LSEE, le conjoint étranger d'un ressortissant suisse a droit à l'octroi et à la prolongation de l'autorisation de séjour. Après un séjour régulier et ininterrompu de cinq ans, il a droit à une autorisation d'établissement. Pour juger de la recevabilité du recours, seule est déterminante la question de savoir si un mariage au sens formel existe (cf. <ref-ruling> consid. 1b p. 266). Le recourant étant toujours marié à une ressortissante suisse, il peut en principe exciper de l'art. 7 al. 1 LSEE le droit au renouvellement de son autorisation de séjour, voire à l'octroi d'une autorisation d'établissement, de sorte que son recours échappe au motif d'irrecevabilité prévu à l'art. 83 let. c ch. 2 LTF.
2.2 Au surplus, déposé en temps utile (<ref-law>) et dans les formes prescrites par la loi (<ref-law>) par le destinataire de l'arrêt attaqué qui a un intérêt digne de protection à son annulation ou à sa modification (<ref-law>), le présent recours, dirigé contre une décision finale prise en dernière instance cantonale par un tribunal supérieur, est en principe recevable au regard des <ref-law>.
3. 3.1 Sous réserve des droits fondamentaux qui doivent être spécialement invoqués et motivés par le recourant (cf. <ref-law>), le Tribunal fédéral applique le droit d'office (<ref-law>). Il fonde son raisonnement juridique sur la base des faits établis par l'autorité précédente (cf. <ref-law>) qu'il ne peut rectifier ou compléter d'office que s'ils ont été constatés de façon manifestement inexacte ou en violation du droit au sens de l'<ref-law> (<ref-law>). Le recourant qui entend invoquer que les faits ont été établis de manière manifestement inexacte (<ref-law>), c'est-à-dire, pour l'essentiel, que les constatations de fait sont arbitraires au sens de l'art. 9 Cst., doit démontrer, conformément aux exigences de l'<ref-law>, par une argumentation précise en quoi consiste la violation. A défaut d'une telle motivation, il n'est pas possible de tenir compte d'un état de fait qui diverge de celui retenu dans la décision attaquée (<ref-ruling> consid. 1.5 p. 68; <ref-ruling> consid. 6.2 p. 288).
3.2 Contrairement à ce que soutient le recourant, le Tribunal fédéral n'a pas à se demander si les époux avaient la volonté de créer une véritable union conjugale, car les juges cantonaux n'ont pas retenu l'existence d'un mariage fictif, au sens de l'art. 7 al. 2 LSEE, c'est-à-dire d'un mariage contracté dans le but d'éluder les dispositions sur le séjour et l'établissement des étrangers. Ils ont uniquement constaté qu'au vu de la longue séparation des époux, devenue définitive à partir du 15 octobre 2005 et clairement confirmée par la police le 20 avril 2006, ainsi que par le recourant lui-même lors de son audition du 6 juillet 2006, l'abus de droit existait déjà avant l'écoulement du délai de cinq ans de l'art. 7 al. 1 LSEE. Dans ces conditions, la juridiction cantonale a estimé que la renonciation de l'épouse à la procédure de divorce, même si celle-ci s'était déterminée de son plein gré, ne suffisait pas pour admettre un espoir de réconciliation.
3.3 Le recourant ne remet pas en cause les constatations de fait de l'arrêt attaqué au sujet de la séparation, mais reproche aux juges cantonaux d'avoir omis de prendre en considération le fait qu'il a versé une contribution d'entretien à son épouse d'un montant de 500 fr. et qu'en mai 2008, le couple a renoncé au divorce. Il prétend qu'ils avaient alors décidé de se donner une nouvelle chance et entrepris des efforts afin de reprendre la vie commune. Il s'agit-là, en réalité, de constatations de fait (indices) permettant de déterminer l'existence d'un abus de droit au regard de l'art. 7 al. 1 LSEE, dont le Tribunal fédéral examine librement la portée juridique, à condition que ces éléments ressortent de l'arrêt attaqué (<ref-ruling> consid. 2.3 p. 152).
Comme on l'a vu (supra consid. 3.2), les juge cantonaux ont bien tenu compte de la renonciation au divorce, mais sans en donner la même portée que le souhaiterait le recourant. Quant à la contribution d'entretien, l'arrêt attaqué ne la mentionne pas. On ne saurait cependant y voir une constatation manifestement inexacte (<ref-law>) ou arbitraire (art. 9 Cst.), dès lors que cet élément n'est pas de nature à modifier le résultat de la décision attaquée, comme il sera démontré ci-après.
4. 4.1 Le droit d'un étranger de séjourner en Suisse pendant la durée du mariage conclu avec une ressortissante suisse n'est pas absolu; il trouve sa limite dans l'interdiction générale de l'abus de droit (<ref-law>; <ref-ruling> consid. 4.2 p. 117). L'existence d'un éventuel abus de droit à invoquer le bénéfice de l'art. 7 al. 1 LSEE doit être appréciée avec retenue et n'être admise que restrictivement; seul l'abus manifeste d'un droit doit être sanctionné (<ref-ruling> consid. 4a p. 103). En particulier, on ne saurait déduire du simple fait que les époux ne vivent pas (ou plus) ensemble l'existence d'un abus de droit, le législateur ayant volontairement renoncé, à l'art. 7 al. 1 LSEE, à faire dépendre le droit à une autorisation de séjour de la vie commune (<ref-ruling> consid. 3 p. 149 ss). En revanche, il y a abus de droit, selon la jurisprudence, lorsque le conjoint étranger invoque un mariage n'ayant qu'une existence formelle dans le seul but d'obtenir une autorisation de séjour, car ce but n'est pas protégé par l'art. 7 al. 1 LSEE. Le mariage n'existe plus que formellement lorsque l'union conjugale est rompue définitivement, c'est-à-dire lorsqu'il n'y a plus d'espoir de réconciliation; les causes et les motifs de la rupture ne jouent pas de rôle (<ref-ruling> consid. 4.2 p. 267 et les arrêts cités). L'absence de cohabitation pendant une période significative constitue un indice permettant de dire que les époux ne veulent plus mener une véritable vie conjugale (<ref-ruling> consid. 10.3 p. 136).
4.2 Il est en l'espèce constant que depuis le 15 octobre 2005 en tout cas, les époux vivent séparés et que la renonciation de l'épouse à poursuivre son action en divorce depuis le mois de mai 2008 n'a pas modifié la situation. Même si, comme le relève le recourant, il appartient à l'autorité d'apporter la preuve que le mariage n'existe plus que formellement, les parties ont cependant l'obligation de collaborer à l'établissement des faits, en particulier lorsque les circonstances objectives du cas permettent sérieusement de douter de la réelle et commune volonté des époux de former une communauté de vie (arrêt 2C_587/2008 du 4 décembre 2008 consid. 4.1). Or, en l'espèce, le recourant n'a pas été en mesure de fournir la moindre preuve sur les soi-disant efforts consentis depuis 2008 par le couple pour reprendre la vie conjugale. Tout indique, au contraire, que les époux n'ont plus aucun intérêt commun et qu'ils n'ont nullement l'intention de vivre à nouveau ensemble. Le recourant a certes produit cinq récépissés postaux attestant un versement mensuel d'un montant de 500 fr. à son épouse dès le mois de juin 2008. Cette contribution d'entretien, qui n'a au demeurant pas été fixée par un tribunal civil, ne suffit toutefois pas pour admettre que le mariage ne serait pas abusif. Le raisonnement a contrario présenté sur ce point par le recourant, tiré de l'<ref-ruling>, consid. 4d p. 104, où le fait de ne pas s'acquitter d'une obligation civile envers l'épouse a été retenu comme un élément à charge, ne saurait être suivi. Au vu de l'absence totale d'indices permettant de supposer une réconciliation des époux en 2008, il faut en déduire que le mariage est maintenu artificiellement dans le seul but de permettre au recourant de demeurer en Suisse. L'invocation de ce mariage pour obtenir la prolongation de l'autorisation de séjour est donc bien constitutive d'un abus de droit.
Dès lors qu'il ressort clairement du dossier que la rupture de l'union conjugale était effective en tout cas depuis le 15 octobre 2005, soit avant l'échéance du délai de cinq ans de l'art. 7 al. 1 LSEE au 2 avril 2006, le recourant ne saurait davantage se prévaloir de la durée de son mariage pour obtenir une autorisation d'établissement.
4.3 Il s'ensuit que la juridiction cantonale n'a pas violé le droit fédéral en confirmant le refus de prolonger l'autorisation de séjour du recourant ou de lui délivrer une autorisation d'établissement.
5. Le recourant invoque encore simultanément les art. 13 et 14 Cst., soit la protection de la sphère privée et du droit au mariage, ainsi que le droit au respect de la vie familiale. Il ne motive toutefois pas ses griefs conformément aux exigences de l'<ref-law>, dans la mesure où il ne dit pas en quoi les droits constitutionnels découlant des art. 13 et 14 Cst. auraient été violés par la juridiction cantonale qui, comme on l'a vu (supra consid. 4), pouvait retenir qu'il n'avait plus aucun lien avec son épouse. Partant, le recours n'est pas recevable en tant qu'il porte sur ces dispositions.
6. Au vu de ce qui précède, le recours doit être rejeté dans la mesure de sa recevabilité. Succombant, le recourant doit supporter les frais judiciaires (<ref-law>) et n'a pas droit à des dépens (<ref-law>).

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 à 2'000 fr., sont mis à la charge du recourant.
3. Le présent arrêt est communiqué au recourant, au Service des migrations, au Département de l'économie et à la Cour de droit public du Tribunal administratif du canton de Neuchâtel, ainsi qu'à l'Office fédéral des migrations.
Lausanne, le 20 août 2009
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: La Greffière:
Müller Rochat