Faits: A. A.X._, ressortissant tunisien né en 1964, a épousé le 19 septembre 1996 B._, de nationalité suisse, dont il avait eu un fils le 23 juillet 1996. Il a été mis au bénéfice d'une autorisation de séjour. Dès le 30 septembre 1998, les époux ont vécu séparés. Un second fils est cependant né le 20 août 1999. Par jugement du 11 juillet 2001, le Tribunal correctionnel du district de Neuchâtel a condamné l'intéressé à une peine de 15 mois d'emprisonnement pour infractions à la loi fédérale sur les stupéfiants. Le Tribunal a ordonné la suspension de l'exécution de la peine au profit d'un traitement en milieu fermé. Le 13 juin 2002, le Tribunal de police du district de La Chaux-de-Fonds a condamné l'intéressé pour infractions à la loi fédérale sur les stupéfiants à 10 jours d'arrêt à titre partiellement complémentaire à la peine prononcée le 11 juillet 2001. Cette peine a également été suspendue au profit d'un traitement. Le 3 novembre 2003, le Service cantonal des étrangers (devenu le Service des migrations) a prolongé jusqu'en septembre 2004 l'autorisation de séjour de l'intéressé. Par jugement du 8 février 2005, le Tribunal civil du district de la Chaux-de-Fonds a prononcé le divorce des époux X._ et confié à la mère l'autorité parentale sur les enfants. Le 23 février 2006, le Tribunal correctionnel de l'arrondissement de Lausanne a condamné l'intéressé pour violations de la loi fédérale sur les stupéfiants à 18 mois d'emprisonnement et ordonné son expulsion du territoire suisse pour une durée de cinq ans. Cette peine a aussi été suspendue au profit d'un traitement. Par courrier du 2 février 2007, le Service des migrations a informé l'intéressé qu'il envisageait de l'expulser de Suisse en raison des condamnations prononcées à son encontre et de sa dette envers l'aide sociale, qui s'élevait à plus de 180'000 fr. pour l'aide reçue entre novembre 1996 et septembre 2006. Le 5 avril 2007, le Service des migrations a prononcé l'expulsion de l'intéressé pour une durée indéterminée. A la suite d'un recours pour violation du droit d'être entendu, le Service des migrations a, le 29 mai 2007, annulé la décision du 5 avril 2007. Le 10 juillet 2007, le Service des migrations a refusé de prolonger l'autorisation de séjour de l'intéressé et lui a fixé un délai de départ au 30 septembre 2007. Le 24 juin 2008, le Département de l'économie du canton de Neuchâtel a rejeté le recours déposé contre ce refus. B. Par arrêt du 13 janvier 2009, le Tribunal administratif du canton de Neuchâtel a rejeté le recours déposé par l'intéressé contre la décision rendue le 24 juin 2008 par le Département de l'économie. Il ressort en substance de cette décision que l'intéressé pouvait invoquer l'art. 8 CEDH pour sauvegarder ses relations personnelles avec ses enfants. Les liens entre eux n'étaient pas particulièrement marqués. Ayant été condamné à de multiples reprises pour infractions à la loi fédérale sur les stupéfiants, l'intéressé n'avait pas eu un comportement irréprochable. Dans ces conditions, il existait un intérêt prépondérant à refuser la prolongation de séjour, quand bien même il avait vécu de longues années en Suisse. Un nouveau délai pour quitter le territoire cantonal devait être fixé. C. Agissant par la voie du recours en matière de droit public, l'intéressé demande au Tribunal fédéral d'annuler la décision rendue le 13 janvier 2009 par le Tribunal administratif et d'ordonner à l'autorité compétente de prolonger son autorisation de séjour. Invoquant l'art. 8 CEDH, il se plaint de ce que le Tribunal administratif a procédé à une pesée arbitraire des intérêts en présence. Il demande à être mis au bénéfice de l'assistance judiciaire gratuite. Le Département de l'économie et le Service des migrations du canton de Neuchâtel ainsi que l'Office fédéral des migrations concluent au rejet du recours. D. Par ordonnance du 19 février 2009, le Président de la IIe Cour de droit public a octroyé l'effet suspensif au recours en matière de droit public. 