Faits: A. X._, ressortissant angolais né en 1973, est arrivé en Suisse en 1990. Il y a déposé une demande d'asile qui a été rejetée. Il a renouvelé sa demande, en 1994, lors de son retour en Suisse. Le 16 août 1995, X._ a épousé, dans son pays d'origine, une citoyenne suisse. Il a alors rejoint notre pays et a obtenu une autorisation de séjour, puis une autorisation d'établissement le 6 septembre 2000. Le divorce des époux X._ a été prononcé par jugement du 10 décembre 2002. Le 29 décembre 2005, l'intéressé s'est remarié avec une ressortissante angolaise, titulaire d'un permis N. Ils ont eu un fils, A._, né le *** 2006, auquel a été délivré une autorisation d'établissement. Par jugement du 25 octobre 2006, le Tribunal correctionnel du district de Boudry a condamné X._ à cinq ans de réclusion et prononcé son expulsion du territoire suisse pour une durée de dix ans, sans sursis. Il a retenu que l'intéressé avait commis des actes d'ordre sexuel avec des enfants en abusant de sa nièce pendant plusieurs années. Il a également été reconnu coupable de vols au préjudice de son employeur et de consommation de stupéfiants. Le 21 août 2007, le Service des migrations du canton de Neuchâtel (ci-après: le Service des migrations) a prononcé l'expulsion de X._ du territoire suisse et a fixé son départ au jour de sa libération. Outre le jugement du 25 octobre 2006, cette décision énumère différentes condamnations prononcées à l'égard de l'intéressé, soit: - condamnation du 5 octobre 1998 à 20 jours d'arrêts avec sursis, et à une amende de 500 fr., pour avoir circulé malgré "un retrait ou un refus du permis de conduire", - condamnation du 9 mars 1999 à 1 mois et 15 jours d'emprisonnement avec sursis pour recel et contravention à la loi sur les stupéfiants, - condamnation du 5 décembre 2000 à une amende de 1'000 fr. avec sursis pour violation grave des règles de la circulation routière, - condamnation du 30 juillet 2002 à 5 jours d'emprisonnement avec sursis, ainsi qu'à une amende de 200 fr., pour vol d'importance mineure et dommages à la propriété, - condamnation du 5 novembre 2002 à 7 jours d'emprisonnement pour violation des règles de la circulation routière et conduite en étant pris de boisson. Le 15 septembre 2008, le Service des migrations a octroyé à l'épouse de X._ une autorisation de séjour en raison des problèmes de santé de A._. Par décision du 9 mars 2009, 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 d'expulsion susmentionnée. B. Le Tribunal administratif du canton de Neuchâtel (ci-après: le Tribunal administratif) a rejeté, par arrêt du 21 août 2009, le recours de l'intéressé à l'encontre de la décision du 9 mars 2009. Il a en substance retenu que les circonstances exceptionnelles, qui seules auraient permis de trancher en faveur de X._ au vu de la gravité des infractions commises, n'étaient pas réalisées. C'était donc à bon droit, et sans abuser de son pouvoir d'appréciation, que le Département de l'économie avait confirmé la décision d'expulsion. C. 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, de dire que son recours est bien fondé et d'annuler l'arrêt du 21 août 2009 du Tribunal administratif. Il invoque une violation des art. 10 et 11 de la loi fédérale du 26 mars 1931 sur le séjour et l'établissement des étrangers (ci-après: LSEE ou loi sur le séjour et l'établissement des étrangers; RS 1 113), en vigueur jusqu'au 31 décembre 2007, de l'art. 8 CEDH, ainsi que des art. 5 et 13 Cst. Le Service des migrations et le Département de l'économie concluent au rejet du recours. Le Tribunal administratif se réfère aux motifs de l'arrêt attaqué et demande le rejet du recours. Il en va de même de l'Office fédéral des migrations. Par ordonnance du 15 octobre 2009, le Président de la IIe Cour de droit public du Tribunal fédéral a rejeté la demande d'effet suspensif. Le 7 janvier et 29 avril 2010, le Service des migrations a spontanément produit divers pièces dont une décision du 6 janvier 2010 en matière de libération conditionnelle. 