Faits:
A. X._, ressortissant sénégalais, né en 1975, est entré en Suisse au mois d'août 1996 et y a déposé une demande d'asile sous une fausse identité. Celle-ci a été rejetée par décision de l'Office fédéral des réfugiés, actuellement l'Office fédéral des migrations (ODM), du 12 mai 1997.
Revenu illégalement en Suisse au mois d'août 1999, X._ a obtenu le relief d'un précédent jugement rendu par défaut. Le Tribunal de police du district de Lausanne l'a alors condamné à trois mois d'emprisonnement, sous déduction de 77 jours de détention préventive, pour faux dans les certificats, infraction à la loi fédérale sur les stupéfiants (LStup; RS 812,121) et infraction à l'ancienne loi fédérale sur le séjour et l'établissement des étrangers (LSEE; RS 1 113). Ce jugement du 11 octobre 1999 a été confirmé par la Cour de cassation pénale du Tribunal cantonal vaudois, le 23 novembre 1999.
Le 13 novembre 2000, X._ s'est marié avec une ressortissante suisse, A._, dont il avait eu une fille prénommée B._, le 7 mars 2000. Partant, le Service de la population du canton de Vaud lui a délivré, en l'assortissant d'un avertissement, une autorisation de séjour au titre de regroupement familial régulièrement renouvelée jusqu'au 6 novembre 2009.
Les époux X._ ont annoncé leur séparation le 27 mars 2002. Ils n'ont jamais ouvert action en divorce, ni repris la vie commune.
Par la suite, X._ a encore été condamné à quatre reprises:
- par ordonnance du Juge d'instruction de l'arrondissement de Lausanne du 4 novembre 2003, à 30 jours d'emprisonnement avec sursis pendant deux ans et à une amende de 1'000 fr. pour entrave à la circulation publique, violation simple de règles de la circulation routière et ivresse au volant;
- par ordonnance du Juge d'instruction de l'arrondissement de Lausanne du 2 novembre 2004, à un mois d'emprisonnement avec sursis pendant trois ans pour violation des règles de la circulation routière et induction de la justice en erreur, le précédent sursis étant révoqué;
- par jugement du Tribunal correctionnel de l'arrondissement de Lausanne du 19 décembre 2008, à douze mois d'emprisonnement avec sursis pendant quatre ans, pour infraction et contravention à la LStup, violations répétées des règles de la circulation routière et instigation à induction de la justice en erreur, sans révocation du sursis précédent;
- par ordonnance du Juge d'instruction de l'arrondissement de Lausanne du 14 août 2009, à cinq jours-amende, valeur à 30 fr., avec sursis pendant deux ans, peine complémentaire à celle du 19 décembre 2008, pour avoir été interpellé, le 12 octobre 2008, en possession d'un couteau papillon, en violation de la loi fédérale sur les armes.
B. Par requête du 14 décembre 2007, X._ a sollicité la prolongation de son autorisation de séjour.
Les autorités communales compétentes ont émis un préavis positif le 3 janvier 2008. Le 7 novembre 2008, le Service cantonal de la population a également donné un préavis favorable à la poursuite du séjour de l'intéressé en Suisse sur la base de l'art. 50 al. 1 let. b de la loi fédérale sur les étrangers (LEtr; RS 142.20), tout en réservant l'approbation de l'ODM et l'issue de la procédure pénale en cours devant le Tribunal correctionnel de l'arrondissement de Lausanne.
Par décision du 15 janvier 2010, l'ODM a refusé d'approuver l'autorisation de séjour de X._ et a prononcé son renvoi de Suisse.
X._ a recouru contre cette décision auprès du Tribunal administratif fédéral en se prévalant de sa situation professionnelle stable, des liens étroits qu'il entretenait avec sa fille et du fait que, dans leur jugement du 19 décembre 2008, les juges lui avaient accordé le sursis et avaient renoncé à révoquer le sursis précédent, en raison de son comportement récent.
C. Le Tribunal administratif fédéral a rejeté le recours, par arrêt du 9 mars 2012. Il a jugé le cas sous l'angle de l'ancien droit (LSEE), tout en relevant que le nouveau droit (LEtr) ne serait pas plus favorable au recourant, puis il a retenu que ce dernier ne pouvait déduire aucun droit à la prolongation de son autorisation de séjour ou à l'octroi d'une autorisation d'établissement sur la base de l'art. 7 al. 1 LSEE. Au vu de la pesée des intérêts en présence opérée au regard de l'art. 8 § 1 CEDH, les premiers juges ont également considéré que le droit de visite que X._ exerçait sur sa fille ne suffisait à reléguer au second plan l'intérêt public à son éloignement de Suisse. Ils ont enfin constaté que rien ne s'opposait au renvoi de l'intéressé au Sénégal, conformément à l'art. 83 al. 4 LEtr.
D. X._ forme auprès du Tribunal fédéral un recours en matière de droit public et conclut, sous suite de frais et dépens, principalement, à la réforme de l'arrêt du Tribunal administratif fédéral du 5 mars 2012, en ce sens que la prolongation de son autorisation de séjour est accordée, subsidiairement, à l'annulation de cet arrêt, la cause étant renvoyée à l'autorité inférieure pour nouvelle décision dans le sens des considérants.
En application de l'<ref-law>, le Tribunal fédéral a ordonné la production des dossiers du Tribunal administratif fédéral, de l'ODM et du Service cantonal de la population sans échange d'écritures.
E. Par ordonnance présidentielle du 8 mai 2012, l'effet suspensif a été accordé au recours.
Le 29 mai 2012, X._ a présenté une demande d'assistance judiciaire et a produit un bordereau de cinq pièces à l'appui. Partant, le Tribunal fédéral a renoncé provisoirement à demander une avance de frais et a informé le recourant qu'il sera statué ultérieurement sur sa demande d'assistance judiciaire.

Considérant en droit:
1. Le litige porte sur le refus d'approuver la prolongation de l'autorisation de séjour du recourant. A juste titre, la décision de renvoi prononcée par les autorités fédérales n'est pas remise en cause dans le recours, car cette question n'est pas de la compétence du Tribunal fédéral (art. 83 let. c ch. 4 LTF). Il n'est par ailleurs pas contesté que la demande d'autorisation de séjour ayant été déposée le 14 décembre 2007, soit avant l'entrée en vigueur, le 1er janvier 2008, de la LEtr, le cas demeure régi par l'ancien droit (cf. art. 126 al. 1 LEtr), à savoir la LSEE.
2. 2.1 Aux termes de l'art. 83 let. c ch. 2 LTF, le recours en matière de droit public est irrecevable contre les décisions relatives à une autorisation de droit des étrangers à laquelle ni le droit fédéral ni le droit international ne donnent droit.
D'après l'art. 7 al. 1 LSEE, le conjoint étranger d'un ressortissant suisse a droit à l'octroi et à la prolongation de l'autorisation de séjour. Après un séjour régulier et ininterrompu de cinq ans, il a droit à une autorisation d'établissement. Pour juger de la recevabilité du recours, seule est déterminante la question de savoir si un mariage au sens formel existe (<ref-ruling> consid. 1b p. 266). Le recourant étant toujours marié à une ressortissante suisse, il peut en principe exciper de l'art. 7 al. 1 LSEE le droit au renouvellement de son autorisation de séjour, voire à l'octroi d'une autorisation d'établissement, de sorte que son recours échappe au motif d'irrecevabilité prévu à l'art. 83 let. c ch. 2 LTF.
En outre, un étranger peut, selon les circonstances, se prévaloir du droit au respect de sa vie privée et familiale garanti par l'art. 8 § 1 CEDH, respectivement 13 al. 1 Cst., pour s'opposer à l'éventuelle séparation de sa famille. Encore faut-il, pour pouvoir invoquer cette disposition, que la relation entre l'étranger et une personne de sa famille ayant le droit de résider durablement en Suisse (nationalité suisse ou autorisation d'établissement) soit étroite et effective (<ref-ruling> consid. 5.3 p. 211 et les arrêts cités). L'art. 8 CEDH s'applique lorsqu'un étranger fait valoir une relation intacte avec ses enfants bénéficiant du droit de résider en Suisse, même si ces derniers ne sont pas placés sous son autorité parentale ou sous sa garde du point de vue du droit de la famille (<ref-ruling> consid. 1d p. 3; arrêt 2C_555/2011 du 29 novembre 2011, consid. 3.1).
En l'espèce, la fille du recourant, âgée de douze ans, est de nationalité suisse, comme sa mère qui en a la garde. Il est par ailleurs établi que, depuis qu'il est séparé de son épouse, le recourant exerce régulièrement et à satisfaction son droit de visite sur sa fille. Dans la mesure où l'arrêt attaqué a des incidences sur les relations personnelles que le recourant entretient avec sa fille, ce dernier peut se prévaloir de l'art. 8 CEDH. Le recours en matière de droit public est donc aussi recevable sous cet angle.
2.2 Au surplus, déposé en temps utile (<ref-law>) et dans les formes prescrites par la loi (<ref-law>), par le destinataire de l'arrêt attaqué qui a un intérêt digne de protection à son annulation ou à sa modification (<ref-law>), le présent recours, dirigé contre une décision du Tribunal administratif fédéral (<ref-law>), est en principe recevable.
3. Le Tribunal fédéral fonde son raisonnement juridique sur les faits constatés par l'autorité précédente (<ref-law>), à moins que ces faits n'aient été établis de façon manifestement inexacte - notion qui correspond à celle d'arbitraire (<ref-ruling> consid. 4.1.2 p. 62; <ref-ruling> consid. 4.3 p. 62) - ou en violation du droit au sens de l'<ref-law> (cf. <ref-law>). Si le recourant entend s'écarter des constatations de fait de l'autorité précédente (cf. <ref-law>), il doit expliquer de manière circonstanciée en quoi les conditions d'une exception prévue par l'<ref-law> seraient réalisées. Sinon, il n'est pas possible de tenir compte d'un état de fait divergent de celui qui est contenu dans l'acte attaqué (cf. <ref-ruling> consid. 5.1 p. 356; <ref-ruling> consid. 3 p. 104). Une rectification de l'état de fait ne peut être demandée que si elle est de nature à influer sur le sort de la cause (<ref-law>). Aucun fait nouveau ni preuve nouvelle ne peut être présenté à moins de résulter de la décision de l'autorité précédente (<ref-law>).
En l'espèce, il n'y a pas lieu de prendre en considération les pièces nouvelles que le recourant produit à l'appui de son recours, en particulier la lettre du 28 mars 2012, rédigée par la mère de sa fille, dont il prétend qu'elle devrait infirmer les constatations de fait de l'autorité intimée au sujet de ses relations avec son enfant, en application de l'<ref-law>. La question de savoir s'il s'agit vraiment d'un fait nouveau résultant de l'arrêt entrepris (cf. <ref-law>) peut demeurer indécise, dans la mesure où il ne motive pas ce grief sous l'angle de l'arbitraire et se contente d'opposer sa thèse à celle de l'autorité au sujet de l'intensité des relations qu'il entretient avec sa fille. Le Tribunal fédéral n'a ainsi aucun motif de s'écarter des faits retenus dans l'arrêt attaqué (<ref-law>).
4. Sous l'angle de l'art. 7 LSEE, le recourant tente de faire valoir que les époux ont maintenu une certaine communauté d'intérêts familiale pour faciliter l'exercice du droit de visite, bien qu'ils soient séparés depuis le 5 avril 2002. Il se prévaut également des diverses mesures protectrices de l'union conjugale, dont les dernières datent du 5 avril 2006, qui confirmeraient que les époux ont essayé de reprendre la vie commune.
Ce faisant, le recourant perd de vue que le droit d'un étranger de séjourner en Suisse pendant la durée du mariage conclu avec une ressortissante suisse n'est pas absolu; il trouve sa limite dans l'interdiction générale de l'abus de droit (<ref-law>; <ref-ruling> consid. 4.2 p. 117). Tel est notamment le cas lorsque, comme en l'espèce, le mariage a duré moins d'une année et demi et n'existe donc plus que formellement, comme le démontre la longue séparation des époux X._ (<ref-ruling> consid. 4.2 p. 267 et les arrêts cités). Les soi-disant tentatives de reprendre la vie commune, qui n'ont pas abouti, ne font que confirmer l'absence de réconciliation possible. Par ailleurs, le recourant ne saurait déduire des intérêts communs des parents à éduquer leur enfant et à organiser le droit de visite du père le maintien d'une certaine communauté familiale, qui subsisterait malgré l'absence de cohabitation (cf. recours p. 6).
Il n'y a ainsi aucun motif de s'écarter de l'état de fait retenu par l'instance précédente (art. 105 al. 1 OJ), constatant que l'union conjugale est rompue définitivement et que le mariage n'existe plus que formellement. La situation du recourant doit donc être examinée uniquement sous l'angle de l'art. 8 CEDH, compte tenu de sa relation avec sa fille.
5. 5.1 Le droit au respect de la vie privée et familiale garanti par l'art. 8 § 1 CEDH n'est pas absolu. Une ingérence dans l'exercice de ce droit est possible selon l'art. 8 § 2 CEDH, pour autant qu'elle soit prévue par la loi et qu'elle constitue une mesure qui, dans une société démocratique, est nécessaire à la sécurité nationale, à la sûreté publique, au bien-être économique du pays, à la défense de l'ordre et à la prévention des infractions pénales, à la protection de la santé ou de la morale, ou à la protection des droits et libertés d'autrui. La question de savoir si, dans un cas d'espèce, les autorités de police des étrangers sont tenues d'accorder une autorisation de séjour fondée sur l'art. 8 CEDH doit être résolue sur la base d'une pesée de tous les intérêts privés et publics en présence (<ref-ruling> consid. 2.1 p. 147; <ref-ruling> consid. 2.2.1 p. 156; <ref-ruling> consid. 2e p. 639; <ref-ruling> consid. 3c p. 5).
Pour ce qui est de l'intérêt privé à obtenir une autorisation de séjour, il faut constater que l'étranger disposant d'un droit de visite sur son enfant habilité à résider en Suisse peut en principe exercer ce droit même s'il vit à l'étranger, au besoin en aménageant ses modalités quant à la fréquence et à la durée de ce droit (cf. arrêt 2C_171/2009 du 3 août 2009 consid. 2.2). La jurisprudence citée par le recourant (cf. ATF <ref-ruling>) en relation avec la révocation d'un titre de séjour du parent qui a la garde de l'enfant, de sorte que son départ entraîne de facto l'obligation pour l'enfant de quitter la Suisse, n'est donc pas pertinente. Pour l'étranger ne bénéficiant que d'un droit de visite, un droit plus étendu peut exister en présence de liens familiaux particulièrement forts dans les domaines affectif et économique et lorsque, en raison de la distance qui sépare le pays de résidence de l'enfant du pays d'origine de son parent, cette relation ne pourrait pratiquement pas être maintenue; le parent qui entend se prévaloir de cette garantie doit cependant avoir fait preuve en Suisse d'un comportement irréprochable (<ref-ruling> consid. 3c p. 5, 22 consid. 4a p. 25; arrêts 2C_1031/2011 du 22 mars 2012, consid. 4.1.4 et les arrêts cités; 2C_679/2009 du 1er avril 2010, consid. 3.1). Un comportement est irréprochable s'il n'existe aucun motif en droit des étrangers d'éloigner ce parent ou de le maintenir à l'étranger, en d'autres termes, s'il ne s'est rendu coupable d'aucun comportement réprimé par le droit des étrangers ou le droit pénal (arrêts 2C_617/2009 du 4 février 2010, consid. 3.1; 2C_723/2008 du 24 novembre 2008, consid. 4.1).
5.2 Il n'est pas contesté que le recourant a de bonnes relations avec sa fille, actuellement âgée de douze ans, qu'il la voit fréquemment et paie la pension mensuelle de 500 fr., allocations familiales comprises, à laquelle il a été astreint par voie de mesures protectrices de l'union conjugale du 5 avril 2006. Les premiers juges ont cependant estimé que les liens du recourant avec sa fille ne dépassaient pas les rapports qu'un parent ne vivant pas avec son enfant et n'ayant pas le droit de garde pouvait entretenir avec celle-ci. Ils ont également relativisé la contribution financière versée par le recourant, en soulignant qu'elle était modeste au regard des 200 fr. d'allocations familiales qu'il touchait. En outre, il avait été à l'aide sociale jusqu'en 2006 et avait dû aussi rembourser cette contribution au Bureau de recouvrement des pensions alimentaires de juin à décembre 2007 (arrêt attaqué p. 14). De toute façon, quelle que soit l'intensité des liens que le recourant dit entretenir avec sa fille, force est de constater qu'ils ne sont pas suffisants au regard du comportement délictueux qu'il a eu en Suisse, depuis son arrivée au mois d'août 1996, où il a déposé une demande d'asile sous l'identité d'un ressortissant mauritanien, jusqu'à sa dernière condamnation du 14 août 2009. Même si, prises isolément, ces condamnations n'atteignent pas un degré de gravité suffisant, bien que l'on puisse hésiter s'agissant de la condamnation de décembre 2008 (cf. <ref-ruling> consid. 4.2 p. 379), elles signifient clairement que le recourant ne parvient pas à se conformer à l'ordre public suisse et que, ni la naissance de sa fille en 2000, ni l'avertissement reçu en 2001 par le Service cantonal de la population ne lui ont permis de s'amender. A cet égard, il faut relever que les préavis favorables des autorités cantonale et communale auxquels il se réfère datent d'avant sa condamnation du 19 décembre 2008 à douze mois d'emprisonnement avec sursis, notamment pour trafic de cocaïne. L'absence de comportement délictueux depuis sa dernière interpellation en octobre 2008 ne suffit pas non plus à effacer les nombreuses infractions qui lui ont été reprochées pendant une dizaine d'années et à admettre qu'il ne représente plus aucun danger pour l'ordre public. Par ailleurs, son intégration socioprofessionnelle reste très limitée. Il travaille certes depuis 2006 dans la même entreprise comme magasinier, mais il a été à l'aide sociale pendant près de six ans et se trouve toujours dans une situation financière difficile.
L'ensemble de ces éléments ne permettent donc pas de s'écarter de la pesée des intérêts opérée par le Tribunal administratif fédéral, qui a abouti à déclarer admissible l'ingérence à la vie familiale du recourant sous l'angle de l'art. 8 CEDH. Ce dernier ne remplit en effet pas les conditions permettant d'obtenir une autorisation de séjour uniquement pour exercer son droit de visite sur sa fille (cf. arrêt 2C_1031/2011 du 22 mars 2012, consid. 4.1.4 et les références citées).
6. Compte tenu de ce qui précède, le recours doit être rejeté dans la mesure de sa recevabilité.
Les conclusions du recours étant dénuées de chances de succès, la demande d'assistance judiciaire doit être également rejetée (<ref-law>). Les frais judiciaires seront ainsi mis à la charge du recourant, en tenant compte de sa situation financière (art. 65 al. 2 et 66 al. 1 LTF).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté dans la mesure où il est recevable.
2. La demande d'assistance judiciaire est rejetée.
3. Les frais judiciaires, arrêtés à 1'000 fr., sont mis à la charge du recourant.
4. Le présent arrêt est communiqué au mandataire du recourant, à l'Office fédéral des migrations et au Tribunal administratif fédéral, Cour III, ainsi que pour information, au Service de la population du canton de Vaud.
Lausanne, le 9 juillet 2012
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: Zünd
La Greffière: Rochat