Faits: A. X._, né en 1974 et ressortissant de la République dominicaine, est entré en Suisse le 19 mai 2001 et a été mis au bénéfice d'une autorisation de séjour au titre de regroupement familial pour vivre auprès de son épouse, Y._, ressortissante suisse, et de leur fille, Z._, née en 2000. Le 28 octobre 2003, A._, la fille de l'intéressé issue d'un premier lit, née en 1992, est entrée en Suisse et a obtenu une autorisation de séjour pour vivre auprès de son père. X._ et son épouse se sont séparés début 2006. Depuis le 1er février 2006, date à laquelle son épouse lui aurait demandé de quitter le domicile conjugal, X._ a touché le revenu d'insertion. Son autorisation de séjour arrivant à échéance le 18 mai 2006, X._ a déposé le 17 avril 2006 une demande de prolongation de celle-ci ainsi qu'une demande de permis d'établissement. Interrogé le 8 juin 2006 en qualité de prévenu pour infraction à la loi fédérale du 3 octobre 1951 sur les stupéfiants et les substances psychotropes (LStup ou loi sur les stupéfiants; RS 812.121), il a déclaré vivre de l'aide des services sociaux dans une chambre d'hôtel à Lausanne avec sa fille A._, dont il avait la charge et avoir un fils âgé de 10 ans vivant avec sa mère en Allemagne. Entendu une nouvelle fois le 20 novembre 2006 pour actes d'ordre sexuel avec des enfants suite aux déclarations de A._, l'intéressé a précisé que, depuis son incarcération pour infraction à la loi sur les stupéfiants, sa fille vivait dans une famille d'accueil, qu'il lui écrivait régulièrement et qu'elle ne lui avait pas répondu. Il avait des nouvelles de A._ par l'intermédiaire de son épouse. Le même jour, cette dernière a déclaré assumer complètement la charge de leur fille Z._ et ne recevoir aucune aide de la part de son mari. Elle a précisé qu'il voyait sa fille une heure toutes les 4 à 5 semaines et que ces visites se passaient bien. Selon l'épouse, si le père de l'enfant devait être renvoyé de Suisse, Z._ serait triste de ne plus le voir de temps en temps. Par jugement du Tribunal correctionnel du 19 décembre 2006, X._ a été condamné à trois ans et demi de réclusion pour infraction grave et contravention à la loi sur les stupéfiants. Il a été incarcéré dans l'établissement pénitentiaire de Bellechasse pour y purger sa peine. La procédure ouverte à son encontre pour infraction d'actes d'ordre sexuel avec des enfants a été close par une ordonnance de non-lieu entrée en force le 27 septembre 2007. Le 10 mars 2008, le Service de la population du canton de Vaud a averti l'intéressé qu'il envisageait de lui refuser le renouvellement de son autorisation de séjour en Suisse et de lui impartir un délai pour quitter le pays dès qu'il aurait satisfait à la justice vaudoise. Par courrier du 21 mars 2008, X._ a répondu qu'il était désolé d'avoir commis une faute, mais qu'il ne voulait surtout pas être séparé de sa fille à laquelle il était très attaché. B. Par décision du 16 mai 2008, le Service de la population a refusé de transformer l'autorisation de séjour de l'intéressé en autorisation d'établissement, subsidiairement de prolonger son autorisation de séjour, et lui a imparti un délai immédiat pour quitter le territoire du canton de Vaud dès qu'il aurait satisfait à la justice vaudoise. Par acte du 17 juin 2008, X._ a recouru contre la décision du 16 mai 2008. Selon lui, sa condamnation ne pouvait à elle seule justifier tout refus de prolongation de son autorisation de séjour. Ayant travaillé en qualité de cuisinier, d'aide-cuisinier ou employé de cuisine à temps partiel pour s'occuper de sa fille Z._, il avait développé des relations très étroites et malgré sa détention, il n'avait jamais cessé d'entretenir d'excellents et réguliers contacts avec elle, cette dernière venant régulièrement lui rendre visite. Une séparation lui causerait des souffrances inutiles et irait à l'encontre de son bon développement. Le 17 juin 2008, le Tribunal cantonal vaudois a accordé l'effet suspensif au recours. L'intéressé a été libéré conditionnellement le 6 octobre 2008. Son divorce a été prononcé le 30 octobre 2008. Selon le jugement transmis le 13 mai 2009, il projette de s'établir en Allemagne. La convention sur les effets accessoires du divorce prévoit que l'autorité parentale et la garde sur Z._ sont attribuées à sa mère et règle le droit de visite. C. Par arrêt du 26 mai 2009, le Tribunal cantonal a rejeté le recours déposé par l'intéressé contre la décision rendue le 16 mai 2009 par le Service de la population. L'intéressé ne pouvait pas se prévaloir de son mariage avec une Suissesse, la séparation datant de 2006 et le divorce du 30 octobre 2008. L'ainée de ses filles ne bénéficiant pas d'un droit de séjour assuré en Suisse, il ne pouvait se prévaloir de l'art. 8 CEDH à son égard. Il n'entretenait pas une relation étroite avec sa deuxième fille et remplissait les conditions d'une expulsion en raison de sa condamnation à trois et demi de réclusion pour infraction grave à la loi sur les stupéfiants. Le refus d'accorder une autorisation d'établissement était ainsi justifié. Celui de renouveler l'autorisation de séjour l'était également d'autant qu'il n'empêchait pas l'intéressé, installé en Allemagne, de garder des contacts avec sa fille en Suisse selon les modalités du droit de visite instituées par le jugement de divorce. Il ne se trouvait pas dans un cas de rigueur. D. Agissant par la voie du recours en matière de droit public, X._ demande au Tribunal fédéral de réformer l'arrêt rendu le 26 mai 2009 par le Tribunal cantonal en ce sens qu'une autorisation de séjour lui est délivrée, subsidiairement de l'annuler et de renvoyer la cause à l'Instance précédente pour nouvelle décision au sens des considérants. Il se plaint de la violation du droit fédéral, de l'art. 8 CEDH et en particulier du principe de proportionnalité. Il sollicite l'assistance judiciaire. Le Tribunal cantonal a renoncé à déposer des observations. L'Office fédéral des migrations conclut au rejet du recours. E. Par ordonnance du 3 juillet 2009, le Président de la IIe Cour de droit public a admis la requête d'effet suspensif déposée par l'intéressé.