Faits: A. A.X._, ressortissant kenyan né en 1972, est arrivé en Suisse en 1995, à la suite de son mariage au Kenya avec B._, ressortissante helvétique. Il a ainsi obtenu une autorisation de séjour. De cette union est née C._ en 1996. Les époux X._ se sont séparés en juillet 1996 et ont divorcé le 23 février 1998. Le jugement de divorce a attribué la garde et l'autorité parentale sur C._ à la mère, a fixé la contribution d'entretien due par le père à 500 fr., a instauré une curatelle éducative et a accordé au père un droit de visite limité, dans un premier temps, à deux heures tous les quinze jours. Par la suite, les modalités du droit visite ont varié. Dès son arrivée en Suisse, A.X._ a régulièrement travaillé comme ouvrier dans diverses entreprises de la région jurassienne. Depuis 2003 toutefois, il bénéficie des prestations de l'aide sociale. Par jugement du 8 mai 2001, le Tribunal correctionnel du canton du Jura a condamné A.X._ à trois mois d'emprisonnement avec sursis pendant trois ans pour lésions corporelles simples et a ordonné son expulsion du territoire suisse pendant cinq ans, avec sursis pendant trois ans. Il a également été condamné le 10 septembre 2002 à une amende de 300 fr. pour perte de maîtrise de son véhicule, le 7 octobre 2003 à une amende de 200 fr. pour non-restitution du permis de circulation et le 21 septembre 2004 à cinq jours d'arrêts avec sursis pendant un an pour conduite inconvenante. En outre, en septembre 2006, A.X._ a passé quarante-quatre jours en détention préventive et a été inculpé de trafic de stupéfiants. B. Le 9 novembre 2006, A.X._ a demandé le renouvellement de son autorisation de séjour. Le Service de la population du canton du Jura (anciennement: le Service de l'état civil et des habitants; ci-après: le Service de la population) a refusé ce renouvellement et a imparti un délai au 31 janvier 2008 à l'intéressé pour quitter ledit canton. Par décision du 6 mai 2008, ce même Service a rejeté l'opposition de A.X._ et lui a imparti un nouveau délai au 30 juin 2008. Il a rejeté sa requête d'assistance judiciaire. Le 29 octobre 2008, l'intéressé a bénéficié d'un classement sans suite dans le cadre d'une dénonciation pour infraction à la loi fédérale sur les armes et a été condamné pour conduite inconvenante. Il a fait opposition à l'ordonnance de condamnation et a été libéré de la prévention de conduite inconvenante. C. Par arrêt du 6 février 2009, le Tribunal cantonal du canton du Jura (ci-après: le Tribunal cantonal) a admis le recours de A.X._ en tant qu'il concernait l'assistance judiciaire au stade de la procédure d'opposition. Il a rejeté le recours pour le surplus et a imparti à l'intéressé un délai au 31 mars 2009 pour quitter la Suisse. Il a également rejeté la demande d'assistance judiciaire pour la procédure de recours. Le Tribunal cantonal a en substance estimé que le recourant n'avait pas de droit à une autorisation de séjour sur la base de l'art. 8 CEDH, le droit de visite de A.X._ n'étant "manifestement pas large ni exercé sans encombre au sens de la jurisprudence". Durant de nombreuses années, père et fille ne s'étaient vus que dans le cadre du point-rencontre, quelques heures un week-end sur deux. Puis, à partir de novembre 2006, l'intéressé ne voyait sa fille qu'à de très rares occasions, même s'il lui téléphonait de manière assez régulière. Le diagnostic de personnalité paranoïaque, et ses répercussions sur le comportement du recourant, ne changeait rien au fait que le droit de visite ne pouvait être qualifié de large. De plus, A.X._ ne s'acquittait plus de la pension alimentaire. Ayant été condamné à plusieurs reprises, l'intéressé n'avait pas eu un comportement irréprochable. Le Service de la population n'avait pas non plus abusé de son pouvoir d'appréciation (art. 4 de la loi fédérale du 26 mars 1931 sur le séjour et l'établissement des étrangers [LSEE, en vigueur jusqu'au 31 décembre 2007; RS 1 p. 113]), compte tenu, notamment, de la mauvaise intégration professionnelle du recourant et de son recours à l'aide sociale depuis 2003, de liens sociaux qui n'étaient pas particulièrement développés et de ses condamnations pénales qui tendaient à démontrer son refus de s'intégrer à l'ordre juridique suisse. D. Agissant par la voie du recours en matière public et, subsidiairement, du recours constitutionnel subsidiaire, A.X._ demande au Tribunal fédéral, sous suite de frais et dépens, d'annuler l'arrêt du Tribunal cantonal du 6 février 2009, de lui accorder une prolongation de son autorisation de séjour, d'éventuellement renvoyer le dossier à l'autorité cantonale pour une nouvelle décision lui octroyant une prolongation de son autorisation de séjour et de le mettre au bénéfice de l'assistance judiciaire pour la procédure devant le Tribunal cantonal; subsidiairement, il lui demande, sous suite de frais et dépens, d'annuler l'arrêt du Tribunal cantonal du 6 février 2009, de l'admettre provisoirement en Suisse et de renoncer à son renvoi, d'éventuellement renvoyer le dossier à l'autorité cantonale pour une nouvelle décision l'admettant provisoirement en Suisse et renonçant à son renvoi et de le mettre au bénéfice de l'assistance judiciaire pour la procédure devant le Tribunal cantonal. Se prévalant de sa relation avec sa fille et de son état psychique, A.X._ invoque l'art. 8 CEDH. Le recourant demande au surplus l'assistance judiciaire pour la présente procédure. Le Tribunal cantonal et l'Office fédéral des migrations concluent au rejet du recours. Le Service de la population n'a pas déposé d'observations. E. Par ordonnance présidentielle du 17 mars 2009, la demande d'effet suspensif a été admise. Le Tribunal cantonal a fait parvenir au Tribunal fédéral, le 24 mars 2009, un rapport de dénonciation du 11 mars 2009 de la Police cantonale du canton du Jura ainsi qu'un procès-verbal d'interrogatoire de A.X._. Le Service de la population a, par courrier du 26 juin 2009, produit un jugement du 19 juin 2009 de la Cour pénale du Tribunal cantonal.