Faits:
A. X._, né le ***1971, est entré illégalement en Suisse, en janvier 2003, et y a travaillé sans autorisation. Le 26 mars 2004, il s'est marié avec A._, ressortissante espagnole, née en 1960, et titulaire d'une autorisation d'établissement. X._ a ainsi obtenu une autorisation de séjour. Le 13 juillet 2004, il a quitté le domicile conjugal avant de le réintégrer le 4 octobre de la même année.
Par décision du 4 janvier 2007, le Service des migrations du canton de Neuchâtel (ci-après: le Service des migrations) a révoqué l'autorisation de séjour de l'intéressé en lui impartissant un délai au 31 janvier 2007 pour quitter le territoire suisse. Il a retenu que les époux s'étaient séparés quatre mois après leur mariage et que la reprise de la vie commune en octobre 2004 n'avait pas duré, ceux-ci s'étant à nouveau séparés peu de temps après. Depuis lors, ils cohabitaient épisodiquement. Compte tenu, notamment, de l'état psychique de A._, il n'existait plus d'élément permettant de croire à une volonté de reprise de la vie commune. Le mariage n'existait plus que formellement et s'en prévaloir constituait un abus de droit. En outre, X._ n'avait pas été capable de s'adapter à l'ordre établi dans notre pays. Il avait, en effet, fait l'objet de rapports de police et avait été condamné pénalement à la suite de l'utilisation frauduleuse de la carte bancaire de son épouse, celle-ci ayant initialement porté plainte avant de se rétracter, compte tenu de la signature par son conjoint d'une reconnaissance de dette. X._ avait également travaillé auprès de différentes entreprises sans être au bénéfice d'une autorisation de travail. Finalement, le dossier ne permettait pas de conclure à un cas de rigueur.
Le 20 novembre 2007, 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._ contre la décision précitée du Service des migrations.
Le 3 mai 2008, l'épouse du recourant est décédée.
B. Par arrêt du 7 mai 2008, la Cour de droit public du Tribunal administratif du canton de Neuchâtel (ci-après: le Tribunal administratif) a rejeté le recours de X._ contre la décision du 20 novembre 2007 du Département de l'économie "en matière de refus de renouvellement d'une autorisation de séjour", l'autorisation de l'intéressé étant entre-temps parvenue à échéance. Il a retenu en substance qu'en se prévalant de son mariage pour obtenir une autorisation de séjour, le recourant commettait un abus de droit. Par ailleurs, il n'y avait aucune raison de lui octroyer une autorisation de séjour à un autre titre.
C. Le 2 juin 2008, X._ a déposé une requête en reconsidération auprès du Service cantonal des migrations invoquant le suicide de son épouse.
En date du 3 juin 2008, X._ a déposé un recours en matière de droit public auprès du Tribunal fédéral. Il y requiert, sous suite de frais et dépens, l'annulation de l'arrêt du Tribunal administratif et le renvoi de la décision à l'autorité intimée afin qu'elle statue à nouveau. Il estime que les faits pertinents ont été établis de façon inexacte et invoque la violation du droit fédéral. Le Service des migrations, le Département de l'économie, le Tribunal administratif, ainsi que l'Office fédéral des migrations concluent au rejet du recours.
Le 3 juin 2008, l'intéressé a également averti le Tribunal fédéral du dépôt de la requête en reconsidération et requis la suspension de l'instruction jusqu'à droit connu dans cette procédure.
Par ordonnance du 11 juin 2008, le Président de la IIeme Cour de droit public du Tribunal fédéral a suspendu la procédure de recours jusqu'à droit connu sur la procédure pendante devant les autorités neuchâteloises.
D. Par décision du 3 juillet 2008, le Service des migrations a déclaré la demande de reconsidération du 2 juin 2008 irrecevable. Le 3 octobre 2008, le Département de l'économie a rejeté le recours interjeté par X._ contre la décision précitée. Le Tribunal administratif a fait de même par arrêt du 27 octobre 2009, à la suite du recours formé contre la décision du 3 octobre 2008. Il a ajouté que, dans la mesure où la requête du 2 juin 2008 devait être considérée comme une demande de révision de l'arrêt rendu par lui-même le 7 mai 2008, celle-ci devait également être rejetée.
Par ordonnance du 14 décembre 2009, le Président de la IIe Cour de droit public du Tribunal fédéral a ordonné la reprise de la procédure.

Considérant en droit:
1. Le Service des migrations a averti le recourant qu'il comptait révoquer l'autorisation de séjour de celui-ci, par courrier du 28 septembre 2006, soit 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). Sous réserve de l'Accord du 21 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), le cas demeure ainsi 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 (<ref-law>). Il contrôle donc librement la recevabilité des recours qui sont déposés devant lui (<ref-ruling> consid. 1 p. 24, 30 consid. 1 p. 31 et la jurisprudence citée).
2.1 Pour déterminer la recevabilité du recours, le Tribunal fédéral se base en principe sur la situation de fait et de droit qui existe lorsqu'il rend son arrêt (<ref-ruling> consid. 1.1.3 p. 149; <ref-ruling> consid. 1b p. 63; <ref-ruling> consid. 1f p. 262 s.), sauf lorsque les conditions de recevabilité dépendent de la situation de droit matériel. Dans ce cas, il n'y a en effet pas de raison de déroger à la règle générale de l'<ref-law> qui interdit les nova, de sorte qu'il y a lieu de se baser sur l'état de fait existant lors du prononcé de la décision attaquée (cf. arrêts 2C_537/2009 du 31 mars 2010 consid. 2.2.1 et les arrêts cités). Le Tribunal de céans doit en effet examiner si l'autorité précédente a correctement appliqué le droit. Or, la prise en compte - sur le plan tant de la recevabilité que du fond - d'une modification des circonstances conduirait à vider ce contrôle de son sens (arrêt 2C_537/2009 du 31 mars 2010 consid. 2.2.1).
L'épouse du recourant est décédée le 3 mai 2008. L'arrêt attaqué date du 7 mai 2008 et ne tient pas compte de cette disparition. On ne peut toutefois pas reprocher au Tribunal administratif d'avoir constaté les faits de façon manifestement inexacte ou en violation du droit. Il ne ressort, en effet, pas du dossier que ledit Tribunal ait été informé du décès survenu quatre jours avant qu'il ne statue et le recourant ne prétend pas que tel aurait été le cas. Partant, le Tribunal de céans ne prendra pas en considération ce fait qui n'a pas été porté à la connaissance de l'autorité précédente.
2.2 Selon 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.
Il ressort du dossier que la femme du recourant était au bénéfice d'une rente entière de l'assurance-invalidité (décision du 20 novembre 2007 du Département de l'économie point 7 p. 2). Entrent ainsi en considération les art. 7 let. c ALCP et 4 al. 1 annexe I ALCP selon lesquels les ressortissants d'une partie contractante et les membres de leur famille ont le droit de demeurer sur le territoire d'une autre partie contractante après la fin de leur activité économique. L'<ref-law> précise que conformément à l'art. 16 de l'accord, il est fait référence au règlement (CEE) 1251/70 et à la directive 75/34/CEE.
Le règlement CEE 1251/70 (réf. no 31970R1251; ci-après: règlement 1251/70) a été abrogé, avec effet au 30 avril 2006, par le règlement (CE) no 635/2006 de la Commission du 25 avril 2006 (réf. no 32006R0635). Son contenu a cependant été repris et le statut des bénéficiaires du droit de demeurer a été amélioré (cf. règlement (CE) no 635/2006 susmentionné point 1) par l'art. 17 de la directive 2004/38/CE du Parlement européen et du Conseil de 29 avril 2004 relative au droit des citoyens de l'Union et des membres de leur famille de circuler et de séjourner librement sur le territoire des Etats membres (réf. no 32004L0038). Toutefois, la note de bas de page de l'<ref-law> précise qu'il est fait référence au règlement 1251/70 "tel qu'en vigueur à la date de la signature de l'accord". Dès lors, bien qu'abrogé, ledit règlement reste valable dans le cadre de l'<ref-law> (Marc Spescha, in Migrationsrecht, 2e éd., 2009, no 2 ad <ref-law>).
L'art. 2 du règlement 1251/70 prévoit:
"1. A le droit de demeurer sur le territoire d'un Etat membre:
"1. A le droit de demeurer sur le territoire d'un Etat membre:
... b) le travailleur qui, résidant d'une façon continue sur le territoire de cet Etat depuis plus de deux ans, cesse d'y occuper un emploi salarié à la suite d'une incapacité de travail. Si cette incapacité résulte d'un accident du travail ou d'une maladie professionnelle ouvrant droit à une rente entièrement ou partiellement à charge d'une institution de cet Etat, aucune condition de durée de résidence n'est requise."
Selon l'art. 3 par. 1 de ce même règlement, les membres de la famille d'un travailleur, visés à l'article 1er du règlement, qui résident avec lui sur le territoire d'un Etat membre, ont le droit d'y demeurer à titre permanent, si le travailleur a acquis le droit de demeurer sur le territoire de cet Etat conformément à l'article 2, et ceci même après son décès.
2.3 Ces dispositions confèrent donc aux membres de la famille d'une personne établie sur le territoire d'un Etat membre en vertu de la libre circulation le droit d'y demeurer à titre permanent à condition qu'ils y résident avec elle et que celle-ci ait acquis elle-même le droit d'y demeurer à titre permanent. Au demeurant, une fois acquis, ce droit perdure même en cas de décès de la personne dont ils dépendent (Alvaro Borghi, La libre circulation des personnes entre la Suisse et l'UE, 2010, no 443 et 444 p. 208; Marc Spescha, op. cit., no 5 ad <ref-law>). Ainsi, l'art. 3 du règlement 1251/70 octroierait un droit de demeurer au recourant, pour autant que son épouse, ait cessé d'"occuper un emploi salarié à la suite d'une incapacité permanente de travail" après deux ans de séjour en Suisse (art. 2 par. 1 let. b du règlement 1251/70).
L'arrêt attaqué ne dit pas sur quelle base l'épouse du recourant a obtenu son permis d'établissement. Il n'est en outre pas possible de déterminer si, avant son incapacité, elle travaillait et si, par conséquent, elle a cessé d'"occuper un emploi salarié à la suite d'une incapacité permanente de travail" (art. 2 par. 1 let. b du règlement 1251/70). Or, c'est à cette condition que le recourant pourrait tirer un droit à une autorisation sur la base de l'art. 3 du règlement 1251/70, et cela pour autant que son épouse résidait depuis plus de deux ans en Suisse lors de la cessation de son activité, ou que son incapacité résultait d'un accident du travail ou d'une maladie professionnelle (art. 2 par. 1 let. b 2e phrase du règlement 1251/70). Ce point et, par conséquent, la question de la recevabilité peuvent toutefois rester ouverts, le recours devant être rejeté sur le fond.
3. 3.1 Le recours en matière de droit public (<ref-law>) peut être formé pour violation du droit selon les art. 95 et 96 LTF. Le Tribunal fédéral applique le droit d'office (<ref-law>). Il n'est donc limité ni par les arguments soulevés dans le recours ni par la motivation retenue par l'autorité précédente; il peut admettre un recours pour un autre motif que ceux qui ont été invoqués et il peut rejeter un recours en adoptant une argumentation différente de celle de l'autorité précédente (cf. <ref-ruling> consid. 1.4 p. 400; <ref-ruling> consid. 1.4.1 p. 254).
3.2 Le Tribunal fédéral statue sur la base des faits établis par l'autorité précédente (<ref-law>), sauf s'ils ont été établis de façon manifestement inexacte ou en violation du droit au sens de l'<ref-law> (<ref-law>). Aucun fait nouveau ni aucune preuve nouvelle ne peut être présenté, à moins de résulter de la décision de l'autorité précédente (<ref-law>). L'on ne saurait en effet reprocher à une autorité d'avoir mal constaté les faits lorsque ceux-ci ont changé après sa décision (<ref-ruling> consid. 2.1 p. 343; <ref-ruling> consid. 2 p. 497 et les arrêts cités).
3.2.1 De même que le Tribunal fédéral ne tient pas compte du décès de l'épouse du recourant dans le cadre de l'examen de la recevabilité du recours, il ne peut prendre en considération, pour le fond de la cause, ce fait survenu quatre jours avant que le Tribunal administratif statue et dont celui-ci n'avait pas connaissance.
3.2.2 Le recourant estime que le Tribunal administratif a établi les faits de manière inexacte en retenant que le lien conjugal entre les époux était irrémédiablement rompu.
L'intéressé ne prétend toutefois pas que l'autorité intimée se serait basée sur des faits erronés ou établis en violation du droit. Il remet en question la qualification et l'appréciation juridique de l'état du lien conjugal ("le Tribunal administratif aurait dû faire preuve de plus de réserve quant à la notion de définitivement rompu", ledit Tribunal "a mis la charrue avant les boeufs en considérant que le lien conjugal était définitivement rompu", etc.) par le Tribunal administratif et soulève ainsi une question de droit que le Tribunal fédéral examine librement (<ref-ruling> consid. 3 p. 184 et l'arrêt cité). La Cour de céans est par conséquent liée par les faits constatés souverainement par le Tribunal administratif (<ref-law>).
4. 4.1 Comme susmentionné, l'art. 3 du règlement 1251/70 octroie un droit de demeurer au recourant, pour autant que son épouse ait cessé d'"occuper un emploi salarié à la suite d'une incapacité permanente de travail" (art. 2 du règlement 1251/70). A supposer que tel soit le cas, se poserait alors la question de l'abus de droit.
4.2 Dans un arrêt de principe (<ref-ruling> consid. 9 p. 129 ss), le Tribunal fédéral a jugé qu'en cas de séparation des époux, il y a abus de droit à invoquer l'<ref-law> lorsque le lien conjugal est vidé de toute substance et que la demande de regroupement familial vise seulement à obtenir une autorisation de séjour pour l'époux du travailleur communautaire. Cette disposition vise, en effet, seulement à faciliter la libre circulation des travailleurs communautaires en accordant aux membres de leur famille un droit de séjour dérivé du leur. Or, selon cet arrêt, lorsque les époux n'entendent définitivement plus vivre ensemble, cet objectif n'est aucunement contrarié par le refus d'autorisation de séjour opposé au conjoint du travailleur, en ce sens que ce dernier n'est ni empêché de rester en Suisse, ni dissuadé de se rendre dans un autre Etat membre de la Communauté européenne à cause d'un tel refus. Le droit de séjour de son conjoint a perdu, en ce qui le concerne, toute raison d'être, et sa suppression ne compromet pas l'efficacité du droit communautaire.
4.3 On ne voit pas pour quelles raisons la jurisprudence concernant l'abus de droit développée à propos de l'époux d'un travailleur ressortissant d'une partie contractante dans le cadre de l'<ref-law> ne s'appliquerait pas au droit de demeurer après la fin de l'activité économique de l'<ref-law>. Aucun motif justifie de traiter différemment les membres de la famille tirant un droit de l'<ref-law> de ceux le faisant de l'<ref-law>. En effet, le droit de demeurer après la fin de l'activité économique découle du droit "originel" de séjourner du travailleur. Le seul fait que le ressortissant communautaire n'exerce plus d'activité lucrative en Suisse, pour différentes raisons - retraite, incapacité de travail, etc. - ne permet pas d'instaurer un régime qui serait plus tolérant relativement au fait de se prévaloir d'un lien conjugal vidé de toute substance dans le seul but de conserver une autorisation de séjour. L'abus de droit s'appliquant au conjoint du travailleur qui invoque un tel lien conjugal, il doit également être opposé au conjoint du travailleur communautaire après la fin de l'activité économique. Ainsi, il apparaît que, en cas de mariage vidé de toute substance, il y a abus de droit à invoquer l'<ref-law> et que les considérations développées dans le cadre de l'<ref-law> s'appliquent mutatis mutandis à l'art. 4 de cette annexe.
5. 5.1 D'après la jurisprudence (<ref-ruling> consid. 4, 8, 9 et 10 p. 116/117 et 127 ss) relative à l'art. 3 par. 1 et 2 let. a annexe I ALCP, le conjoint étranger d'un travailleur communautaire disposant d'une autorisation de séjour ou d'établissement en Suisse peut se prévaloir de droits d'une portée analogue à ceux dont bénéficie le conjoint étranger d'un citoyen suisse en vertu de l'art. 7 al. 1 LSEE.
Par conséquent, à l'instar des étrangers mariés à un citoyen suisse, les étrangers mariés à un travailleur communautaire jouissent, en principe, d'un droit de séjour en Suisse pendant toute la durée formelle du mariage, attendu qu'ils n'ont pas à vivre "en permanence" sous le même toit que leur époux pour être titulaire d'un tel droit. Ce droit n'est cependant pas absolu. Il y a notamment abus de droit à invoquer cette disposition lorsque le lien conjugal est vidé de toute substance et que la demande de regroupement familial vise seulement à obtenir une autorisation de séjour pour l'époux du travailleur communautaire. A cet égard, les critères élaborés par la jurisprudence rendue à propos de l'art. 7 al. 1 LSEE s'appliquent mutatis mutandis (<ref-ruling> consid. 9.5 p. 134; cf. aussi arrêt 2C_530/2009 du 2 mars 2010 consid. 3.1).
S'il n'est pas obligatoire que les époux vivent ensemble, il faut que demeure la possibilité d'une reprise de la vie commune. Des indices clairs et concrets que tel ne sera pas le cas permettent de conclure au caractère abusif de la requête (<ref-ruling> consid. 2.2 p. 151). L'absence de cohabitation pendant une période significative constitue, notamment, un indice permettant de dire que les époux ne veulent plus mener une véritable vie conjugale. Sauf circonstances particulières, on doit considérer le lien conjugal comme vidé de son contenu deux ans après la fin de la vie commune (<ref-ruling> consid. 10.3 et 10.4 p. 135 ss).
5.2 En l'espèce, il ressort de l'arrêt attaqué que le recourant et son épouse se sont séparés moins de quatre mois après leur mariage conclu le 26 mars 2004. Le 2 août 2004, l'épouse a déposé une plainte pénale à l'encontre de son mari, celui-ci ayant utilisé sa carte bancaire à son insu. Le mandataire du recourant a annoncé la reprise de la vie commune des intéressés en octobre 2004. Cela n'a pas duré puisque les époux ont à nouveau vécu séparément peu après, le recourant se contentant de passer de temps à autre au domicile conjugal. Le Tribunal administratif a aussi constaté que, le 14 juin 2005, l'intéressée a déclaré à la police qu'elle avait demandé à son époux de quitter le domicile conjugal et que celui-ci avait conclu un mariage de complaisance. Un rapport de police du 16 septembre 2006 mentionne que A._ s'est plainte du fait que son époux entretiendrait une relation amoureuse avec sa chienne pour finalement déclarer qu'elle voulait faire partir son mari de son appartement.
Le recourant ne conteste pas qu'il a parfois vécu à l'hôtel et que son couple a connu des périodes difficiles. Selon lui, celles-ci étaient dues aux crises de sa femme qui se montrait violente. Il prétend s'être séparé de A._ à cause des troubles psychiques dont elle souffrait. La séparation des époux n'aurait toutefois été que provisoire et les "sentiments" du recourant envers sa femme n'auraient jamais disparu. L'intéressé n'invoque cependant aucun élément concret et vraisemblable permettant d'admettre une volonté réelle de reprise de la vie commune. La nouvelle cohabitation d'octobre 2004 faisait suite au courrier du 24 août 2004 du Service des migrations informant le recourant de l'intention dudit Service de ne pas renouveler son autorisation de séjour au vu de la séparation des époux X._ - A._ et est ainsi peu probante. De plus, aucune tentative de vie commune n'a duré. Le recourant affirme s'être séparé de sa femme à cause des troubles psychiques de celle-ci. A._ a, en effet, effectué plusieurs séjours à l'hôpital psychiatrique. Or, abstraction faite de son décès que le Tribunal fédéral ne peut pas prendre en compte, rien dans le dossier ne permet de dire que l'épouse du recourant irait mieux et que ses problèmes seraient réglés. Quant aux déclarations de A._ (cf. fin du paragraphe précédent), elles ne vont manifestement pas dans le sens d'une réconciliation. Toutefois, compte tenu des problèmes psychiques de celle-ci, il convient de considérer ces dires avec précaution. Finalement, si, comme le relève le recourant, les époux n'ont effectivement pas à vivre en permanence sous le même toit, l'absence de cohabitation récurrente dans le cas d'espèce constitue un indice supplémentaire permettant de conclure qu'il n'y a pas d'espoir tangible de restauration d'une vraie vie conjugale.
5.3 Ainsi, en se prévalant d'un mariage purement formel pour conserver son autorisation de séjour, le recourant a commis un abus de droit, ce que le Tribunal administratif a dûment constaté sans violer l'Accord. En outre, le lien conjugal n'ayant jamais vraiment existé - le recourant s'étant déjà séparé de sa femme après quatre mois de mariage - le recourant n'a pas acquis le droit de demeurer avant que l'abus de droit ne soit commis.
Le Tribunal administratif a également respecté la loi fédérale sur le séjour et l'établissement des étrangers, le recourant ne pouvant tirer de droit de l'art. 17 al. 2 LSEE puisque, d'une part, les époux ne vivent plus ensemble et qu'une reprise de la vie commune ne peut être sérieusement envisagée à brève échéance (cf. <ref-ruling> consid. 4.1 p. 116) et que, d'autre part, ils étaient séparés avant l'échéance du délai de cinq ans.
6. Le recourant invoque l'art. 50 LEtr qui prévoit qu'après dissolution de la famille, le droit du conjoint et des enfants à l'octroi d'une autorisation de séjour et à la prolongation de sa durée de validité en vertu des art. 42 et 43 LEtr subsiste lorsque l'union conjugale a duré au moins trois ans et l'intégration est réussie (al. 1 let. a). L'intéressé met précisément en avant sa bonne intégration.
Si tous les éléments déterminants d'une cause se sont déroulés, comme c'est le cas en l'espèce, avant l'entrée en vigueur de la loi sur les étrangers, celle-ci reste alors soumise, respectivement est traitée en application de la loi précédemment en vigueur, soit la loi sur le séjour et l'établissement des étrangers (arrêt 2C_530/2009 du 2 mars 2010 consid. 5). D'autre part, comme susmentionné, le Tribunal de céans ne peut tenir compte du décès de l'épouse du recourant pour statuer sur le fond de la présente cause (cf. supra consid. 3.2.1). Partant, l'art. 50 LEtr n'est pas applicable à la présente cause et le grief est irrecevable.
7. Compte tenu de ce qui précède, le recours doit être rejeté dans la mesure où il est recevable.
Succombant, le recourant doit supporter les frais de l'instance (<ref-law>) et il n'est pas alloué de dépens (art. 68 al. 1 et 3 LTF).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté dans la mesure où il est recevable.
2. Les fais 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 18 juin 2010
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: La Greffière:
Zünd Kurtoglu-Jolidon