Faits:
A. Le 14 novembre 2003, X._, de nationalité australienne, a épousé Y._, ressortissante suisse et obtenu une autorisation de séjour, renouvelée pour la dernière fois le 14 novembre 2006.
Informé que le couple était séparé depuis le mois de janvier 2006, le Service des migrations du canton de Neuchâtel a avisé l'intéressé le 12 juin 2007, qu'il envisageait de ne pas renouveler son permis de séjour. Exerçant son droit d'être entendu, ce dernier a indiqué que la séparation, qui était due à des incompatibilités d'horaire de travail avec une vie de couple, n'était pas définitive. Même si une procédure de divorce était en cours, il conservait l'espoir d'une reprise de la vie commune.
Par décision du 22 avril 2008, le Service des migrations a refusé de prolonger l'autorisation de séjour de X._ et lui a fixé un délai de départ au 30 mai 2008. Par décision du 22 août 2008, le Département de l'économie a rejeté le recours de l'intéressé contre la décision du 22 avril 2008.
B. Par arrêt du 3 décembre 2008, le Tribunal administratif du canton de Neuchâtel a rejeté le recours de l'intéressé contre la décision rendue le 22 août 2008 par le Département de l'économie. Il a jugé en substance que l'intéressé abusait du droit en invoquant son mariage dans le but de ne pas perdre son autorisation de séjour, du moment que les époux étaient séparés depuis plus de trois ans et qu'aucun élément concret ne laissait supposer une volonté commune de reprise de la vie de couple. Il n'y avait en outre aucune situation d'extrême rigueur qui justifiait l'octroi d'une autorisation de séjour.
Le Tribunal administratif et le Département de l'économie du canton de Neuchâtel ainsi que l'Office fédéral des migrations concluent au rejet du recours.
C. Par ordonnance du 26 janvier 2009, le Président de la IIe Cour de droit public a admis la demande d'effet suspensif formulée par l'intéressé.

Considérant en droit:
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 LEtr, les demandes déposées avant l'entrée en vigueur de la loi sont régies par l'ancien droit. L'autorisation de séjour du recourant a été renouvelée pour la dernière fois jusqu'au 14 novembre 2006. La procédure de non-renouvellement ayant été initiée avant le 1er janvier 2008, la présente affaire doit être examinée à la lumière de l'ancienne loi fédérale sur le séjour et l'établissement des étrangers (LSEE).
2. 2.1 Selon l'art. 83 lettre c ch. 2 de la loi du 17 juin 2005 sur le Tribunal fédéral (LTF; RS 173.110), 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.
En vertu de 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. Pour juger de la recevabilité du recours en matière de droit public, seule est déterminante la question de savoir si un mariage au sens formel existe (cf. arrêt 2C_701/2008 du 26 février 2009, consid. 3; <ref-ruling> consid. 1b p. 266). Le recourant est marié à une Suissesse. Son recours est donc recevable sous cet angle. La question de savoir si le refus de renouveler l'autorisation de séjour se justifie en raison d'un abus du droit prévu à l'art. 7 LSEE ne concerne pas la recevabilité du recours, elle doit être examinée au fond (<ref-ruling> consid. 1b p. 266 et les références citées).
Le recours en matière de droit public est en revanche irrecevable contre les décisions en matière de droit des étrangers qui con-cernent les exceptions aux nombres maximums (art. 83 lettre c ch. 5 LTF), de sorte que le grief du recourant relatif à la violation de l'art. 13 lettre f de l'ordonnance du 6 octobre 1986 limitant le nombre des étrangers (OLE; RO 1986 1791) est irrecevable.
2.2 Au surplus, interjeté par une partie directement touchée par la décision attaquée et qui a un intérêt digne de protection à son annulation ou sa modification (<ref-law>), le recours est dirigé contre un jugement rendu dans une cause de droit public (<ref-law>) par une autorité cantonale supérieure de dernière instance (art. 86 al. 1 lettre d et al. 2 LTF). Déposé dans le délai (<ref-law>) et la forme (<ref-law>) prévus par la loi, il est en principe recevable.
3. 3.1 Le Tribunal fédéral statue sur la base des faits constatés par l'autorité précédente (cf. <ref-law>), à moins que ces faits n'aient été établis de façon manifestement inexacte ou en violation du droit au sens de l'<ref-law> (cf. <ref-law>). La notion de "manifestement inexacte" de l'<ref-law> correspond à celle d'arbitraire au sens de l'art. 9 Cst. (<ref-ruling> consid. 7.1 p. 398). Enfin, selon l'<ref-law>, aucun fait nouveau ni preuve nouvelle ne peut être présenté à moins de résulter de la décision de l'autorité précédente.
3.2 Le recourant fait état du jugement du Tribunal civil du district de Neuchâtel du 15 décembre 2008. Cet élément de fait est irrecevable, puisqu'il est postérieur à la date à laquelle a été rendu l'arrêt attaqué.
Le recourant fait aussi référence à des événements qui ne ressortent pas des faits constatés par le Tribunal administratif, sans exposer conformément aux exigences de motivation de l'<ref-law> en quoi les constatations de l'arrêt attaqué sont manifestement inexactes. Dans ces conditions, il n'est pas possible de tenir compte d'un état de fait qui diverge de celui retenu dans l'arrêt attaqué. En particulier, il est exclu de prendre en considération la lettre du 5 décembre 2007 de Y._ ni le courrier reçu le 14 février 2007 par une société présentée comme l'employeur du recourant.
4. 4.1 Selon 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 à l'autorisation d'établissement; ce droit s'éteint lorsqu'il existe un motif d'expulsion. Quant à l'art. 7 al. 2 LSEE, il prévoit que le conjoint étranger d'un ressortissant suisse n'a pas droit à l'octroi ou à la prolongation de l'autorisation de séjour, lorsque le mariage a été contracté dans le but d'éluder les dispositions sur le séjour et l'établissement des étrangers et notamment celles sur la limitation du nombre des étrangers. D'après la jurisprudence, le fait d'invoquer l'art. 7 al. 1 LSEE peut être constitutif d'un abus de droit, en l'absence même d'un mariage contracté dans le but d'éluder les dispositions sur le séjour et l'établissement des étrangers au sens de l'art. 7 al. 2 LSEE (<ref-ruling> consid. 4.2 p. 117; <ref-ruling> consid. 5a p. 56 et la jurisprudence citée).
L'existence d'un abus de droit découlant du fait de se prévaloir de l'art. 7 al. 1 LSEE ne peut être simplement déduit de ce que les époux ne vivent plus ensemble, puisque le législateur a volontairement renoncé à faire dépendre le droit à une autorisation de séjour du conjoint étranger d'un ressortissant suisse de la vie commune (cf. <ref-ruling> consid. 3 p. 149 ss). Pour admettre l'existence d'un abus de droit, il ne suffit pas non plus qu'une procédure de divorce soit entamée; le droit à l'octroi ou à la prolongation d'une autorisation de séjour subsiste en effet tant que le divorce n'a pas été prononcé, car les droits du conjoint étranger ne doivent pas être compromis dans le cadre d'une telle procédure. Enfin, on ne saurait uniquement reprocher à des époux de vivre séparés et de ne pas envisager le divorce. Toutefois, il y a abus de droit lorsque le conjoint étranger invoque un mariage n'existant plus que formellement 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; <ref-ruling> consid. 4.2 p. 117 et les arrêts cités).
4.2 Le recourant reproche à l'autorité précédente d'avoir admis, sans faire preuve de la retenue commandée par la jurisprudence, qu'il était abusif de sa part de se prévaloir de son mariage. Il fait valoir que son union avec Y._ ne constituait pas un mariage de complaisance. En outre, il ne commettrait pas un abus de droit en se prévalant de son mariage, car il existerait encore un espoir de réconciliation, le simple fait de ne plus vivre avec son épouse ne permettant pas de conclure à un abus de droit.
Le point déterminant est la question de savoir s'il y a encore un espoir de réconciliation entre les époux, de sorte que leur union ne serait pas rompue définitivement et qu'il ne serait pas abusif de la part du recourant de s'en prévaloir. Les autorités cantonales n'ont en revanche jamais prétendu que le mariage en question aurait été un mariage de complaisance, de sorte que cette question n'a pas à être examinée plus avant.
Les époux ont vécu ensemble moins de deux ans et demi (du 14 novembre 2003 au mois de janvier 2006). Lorsque le Service cantonal des migrations a statué, ils étaient séparés depuis deux ans et quand l'instance précédente a statué sur recours, ils l'étaient depuis plus de deux ans et demi. Cette dernière a en outre constaté qu'aucune tentative de reprise de la vie commune n'avait été tentée, que la procédure de divorce avait été engagée, ce qui n'établissait nullement une éventuelle réconciliation. Le recourant fait à cet égard référence à la volonté interne des époux d'éventuellement reprendre la vie commune. Cette volonté relève des faits. Une fois établis par l'instance précédente, ces faits lient le Tribunal fédéral conformément à l'<ref-law>. Comme le recourant n'a pas démontré en quoi les faits avaient été établis de façon manifestement inexacte ou contraire au droit (<ref-law>), il faut retenir avec l'instance précédente que le mariage entre le recourant et Y._ est vidé de sa substance. Dans ces circonstances, l'instance précédente pouvait admettre qu'il était abusif de la part du recourant de se prévaloir de son mariage dans le seul but de s'opposer au refus de renouvellement de son autorisation de séjour. Partant, le grief de violation de l'art. 7 LSEE est mal fondé et doit être rejeté.
4.3 Le grief de violation de l'interdiction de l'arbitraire tiré de l'art. 9 Cst., qui se confond avec la violation du droit fédéral, en l'espèce de l'art. 7 LSEE, doit être rejeté pour les mêmes raisons.
5. Les considérants qui précèdent conduisent au rejet du recours, dans la mesure où il est recevable. Succombant, le recourant supporte 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 à 1'500 fr., sont mis à la charge du recourant.
3. Le présent arrêt est communiqué au mandataire du 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 29 mai 2009
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: Le Greffier:
Müller Dubey