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. 