Faits: A. X._ (ci-après: le recourant ou l'intéressé), ressortissant turc né en 1970, est entré illégalement en Suisse en 2001. Le 16 janvier 2003, il a épousé A._ née B._, ressortissante française au bénéfice d'une autorisation d'établissement et s'est vu octroyer une autorisation annuelle de séjour. Le 17 janvier 2006, il a annoncé au service des signalements de la police cantonale du canton de Neuchâtel la disparition de son épouse. Un rapport de police du 22 janvier 2006 confirmait le départ de celle-ci en compagnie de C._ en janvier 2006. Ils n'avaient pas laissé de nouvelle adresse. Le contrôle des habitants de Y._ a également établi que A._ avait noué des relations intimes avec C._, lequel avait déposé ses papiers à Y._ le 29 octobre 2005 et habitait à la même adresse que celle-ci. B. Le 5 décembre 2007, le Service des étrangers du canton de Neuchâtel (actuellement et ci-après: le Service des migrations) a averti X._ qu'il ne comptait pas prolonger son autorisation de séjour, étant donné que celui-ci ne vivait plus de manière régulière avec son épouse depuis le début janvier 2006, date du départ de cette dernière. Par décision du 30 avril 2008, le Service des migrations n'a pas prolongé l'autorisation annuelle de séjour (permis B CE/AELE) de X._ et lui a imparti un délai échéant au 15 juin 2008 pour quitter le territoire cantonal. L'autorisation de séjour annuelle était entretemps, soit le 16 janvier 2008, arrivée à échéance. Le 18 décembre 2008, le Conseiller d'Etat, Chef du Département de l'économie du canton de Neuchâtel (ci-après: le Conseiller d'Etat), a rejeté le recours interjeté par X._ contre la décision du Service des migrations. C. Par arrêt du 26 juin 2009, le Tribunal administratif du canton de Neuchâtel (ci-après: le Tribunal administratif) a rejeté le recours de X._. Il a notamment retenu que le fond de l'affaire relevait encore de la loi fédérale du 26 mars 1931 sur le séjour et l'établissement des étrangers (LSEE ou la loi sur le séjour et l'établissement des étrangers; RS 1 113; en vigueur jusqu'au 31 décembre 2007). L'intéressé se prévalait d'un mariage qui n'avait plus aucun contenu, ce qui constituait un abus de droit et rendait caduc tout droit à une autorisation. Le Tribunal administratif a également retenu que le recourant ne pouvait se prévaloir d'une situation d'extrême rigueur susceptible de conduire à l'octroi d'une autorisation de séjour après la dissolution du mariage ou de la communauté conjugale. D. 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 Tribunal administratif du 26 juin 2009 et de prolonger son autorisation de séjour, subsidiairement, de renvoyer le dossier à "l'intimé" pour complément d'instruction ou pour qu'il soit statué dans le sens des considérants. Le Service des migrations, le Conseiller d'Etat, ainsi que le Tribunal administratif, sans formuler d'observations, concluent au rejet du recours. L'Office fédéral des migrations a déposé des observations hors délai. Par ordonnance du 3 septembre 2009, le Président de la IIe Cour de droit public du Tribunal de céans a admis la requête d'effet suspensif. 