Faits:
A. A.X._, ressortissant algérien, né en 1974, est entré illégalement en Suisse dans le courant de l'année 2002, en se légitimant au moyen d'une fausse carte d'identité française. Le 28 mars 2003, il a épousé, à La Chaux-de-Fonds, une ressortissante suisse, B._, née en 1979, et a obtenu une autorisation de séjour dans le canton de Neuchâtel, régulièrement renouvelée jusqu'au 28 mars 2007. Une enfant prénommée C._, née en 2004, est issue de cette union.
Après une première séparation en septembre 2004, les époux ont repris la vie commune au mois d'octobre 2005. Toutefois, lors de l'audience du 29 janvier 2007 devant le Tribunal civil du district de La Chaux-de-Fonds, les époux X._ ont convenu de vivre séparés pour une durée indéterminée, la garde de l'enfant C._ étant attribuée à la mère. Les époux ont également réglé le droit de visite du père, qui s'est engagé à verser une contribution d'entretien mensuelle de 200 fr., puis de 470 fr. à partir du 1er mars 2007.
B. A.X._ a exercé régulièrement son droit de visite et à satisfaction depuis 2004, selon le curateur de l'enfant. En revanche, l'intéressé ne s'est jamais acquitté de la pension alimentaire qu'il s'était engagé à verser pour sa fille et devait à ce titre, au 4 mai 2009, une somme de 13'290 fr, dont 10'300 fr. à l'Etat de Neuchâtel.
Sur le plan professionnel, A.X._ a travaillé du 1er novembre 2003 au 30 avril 2005 pour Y._. Il a bénéficié ensuite des indemnités de l'assurance chômage puis, de mars 2007 à novembre 2008, il a touché le revenu d'insertion dans le canton de Vaud pour un montant de 28'141 fr. 05.
Au 26 juin 2007, A.X._ faisait l'objet de 22 poursuites, pour un montant de 39'197 fr. 30.
Devant l'instance cantonale, il a établi qu'il s'était vu confier par Z._ une mission temporaire d'une durée de trois mois dès le 2 mars 2009 et qu'il avait également trouvé une activité d'employé de vestiaire dans un night club (de 0 à 17 h. par semaine), rémunérée à un tarif horaire de 18 fr. brut.
Sur le plan pénal, A.X._ a été condamné à plusieurs reprises, à savoir:
- par ordonnance du Juge d'instruction de l'arrondissement de Lausanne, du 19 novembre 2002, à une peine d'un mois d'emprisonnement, sous déduction de 22 jours de détention préventive, avec sursis pendant 2 ans, pour vol ;
- par ordonnance du Juge d'instruction de l'arrondissement de la Côte du 3 mai 2006, à une peine d'un mois d'emprisonnement pour vol et utilisation frauduleuse d'un ordinateur, faux dans les certificats et infraction à la loi fédérale sur le séjour et l'établissement des étrangers;
- par prononcé du Ministère public du canton de Neuchâtel du 18 mai 2006, à une amende de 300 fr. pour avoir facilité le séjour illégal d'un étranger;
- par prononcé du Ministère public du canton de Neuchâtel du 26 septembre 2007, à une peine pécuniaire de 15 jours-amendes à 20 fr., avec sursis pendant 2 ans, et à une amende de 300 fr., pour obtention frauduleuse d'une prestation;
- par décision du Préfet du district de Lavaux du 28 novembre 2007, à une peine pécuniaire de 10 jours-amende à 50 fr., avec sursis pendant 2 ans (révoqué), et à une amende de 400 fr., pour violation grave des règles de la circulation routière;
- par ordonnance de la Juge d'instruction du Jura bernois - Seeland du 23 juin 2008, à une amende de 400 fr. pour excès de vitesse et, en cas de non-paiement, à une peine privative de liberté de substitution de 4 jours;
- par ordonnance du Juge d'instruction de l'arrondissement de Lausanne du 12 décembre 2008, à une peine de 30 jours-amende à 30 fr., pour conduite d'un véhicule dans le cadre de son activité professionnelle malgré une mesure de retrait de permis, violation d'une règle de l'ordonnance sur la circulation routière (téléphone au volant) et omission de l'annonce de son changement d'adresse dans les délais; à cette occasion, le Juge a également révoqué le sursis accordé à l'intéressé le 28 novembre 2007 et ordonné l'exécution de la peine de pécuniaire de 10 jours-amendes à 50 fr.
C. A.X._ est arrivé dans le canton de Vaud le 30 mars 2007 et a sollicité le renouvellement de l'autorisation de séjour qui lui avait été délivrée dans le canton de Neuchâtel. Cette requête a été rejetée par décision du Service cantonal de la population du 8 décembre 2008.
Saisi d'un recours contre cette décision, le Tribunal cantonal (Cour de droit administratif et public), l'a rejeté, par arrêt du 24 août 2009.
D. Agissant par la voie du recours en matière de droit public, A.X._ conclut, avec suite de frais et dépens, à la réformation de l'arrêt cantonal du 24 août 2009, en ce sens que son autorisation de séjour est renouvelée, subsidiairement doit être renouvelée. Le recourant demande également d'être mis au bénéfice de l'assistance judiciaire complète devant le Tribunal fédéral.
Le Tribunal cantonal a renoncé à déposer une réponse et se réfère aux considérants de son arrêt. Le Service de la population a également renoncé à se déterminer. De son côté, l'Office fédéral des migrations propose de rejeter le recours.
Par ordonnance présidentielle du 25 septembre 2009, la demande d'effet suspensif présentée par le recourant a été admise.

Considérant en droit:
1. Le litige porte sur le droit du recourant d'obtenir le renouvellement de son autorisation de séjour. La demande ayant été déposée le 30 mars 2007, soit avant l'entrée en vigueur, le 1er janvier 2008, de la loi fédérale sur les étrangers du 16 décembre 2005 (LEtr; RS 142.20), le cas demeure régi par l'ancien droit (cf. art. 126 al. 1 LEtr), à savoir la loi fédérale du 26 mars 1931 sur le séjour et l'établissement des étrangers (LSEE; RS 1 113).
2. Le Tribunal fédéral examine d'office sa compétence et la recevabilité des recours qui lui sont soumis (cf. <ref-law>; <ref-ruling> consid. 1 p. 24; <ref-ruling> consid. 1 p. 431, 483 consid. 1 p. 485).
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 (cf. <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. 1.3.1 p. 145; <ref-ruling> consid. 3.1 p. 285 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; <ref-ruling> consid. 1c p. 84; <ref-ruling> consid. 1c p. 157 et les références).
En l'espèce, la fille du recourant, âgée de six ans, est de nationalité suisse, comme sa mère qui en a la garde. Dans son arrêt, le Tribunal cantonal a constaté 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 finale prise en dernière instance cantonale par un tribunal supérieur, est en principe recevable au regard des <ref-law>.
2.3 Sous réserve des droits fondamentaux qui doivent être spécialement invoqués et motivés par le recourant (cf. <ref-law>), le Tribunal fédéral applique le droit d'office (<ref-law>). Il fonde son raisonnement juridique sur les faits établis par l'autorité précédente (cf. <ref-law>) qu'il ne peut rectifier ou compléter d'office que s'ils ont été constatés de façon manifestement inexacte ou en violation du droit au sens de l'<ref-law> (<ref-law>). Dans cette mesure, 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>). Une exception doit également être admise lorsque les faits postérieurs à la décision attaquée déterminent la recevabilité du recours (<ref-ruling> consid. 1.1.3 p. 140; arrêts 2C_54/2009 du 28 novembre 2008, consid. 2.2, 2C_591/2008 du 24 novembre 2008, consid. 2.2). A cet égard la convention non datée passée entre les époux, que le recourant produit devant le Tribunal fédéral, démontre seulement que ceux-ci ont décidé de déposer une requête commune en vue du prononcé de leur divorce, ce que l'arrêt attaqué invoque du reste, mais n'est pas de nature à prouver un divorce imminent et un remariage possible dans un délai proche. Cette pièce doit donc être écartée en application de l'<ref-law>. Il en va de même de l'attestation de l'Office des poursuites de l'arrondissement de Lausanne-Ouest du 17 septembre 2009, destinée à prouver que la situation financière du recourant s'est améliorée.
3. Le recourant admet que la séparation avec son épouse est définitive et que le lien conjugal est définitivement rompu, de sorte qu'il ne prétend pas au renouvellement de son autorisation de séjour sur la base de l'art. 7 al. 1 LSEE. Il se prévaut essentiellement de sa relation avec sa fille, ainsi que de sa nouvelle liaison avec une ressortissante suisse, avec laquelle il serait en ménage depuis le mois de février 2008 et qu'il aurait l'intention d'épouser.
Ces faits montrent que l'union conjugale est rompue définitivement et que le mariage n'existe plus que formellement (<ref-ruling> consid. 4.2 p. 267; <ref-ruling> consid. 4.2 p. 117 et les arrêts cités), de sorte que la situation du recourant doit être examinée uniquement sous l'angle de l'art. 8 CEDH, compte tenu de sa relation avec sa fille.
3.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. 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 (cf. arrêt 2C_171/2009 du 3 août 2009 consid. 2.2). 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; en outre, le parent qui entend se prévaloir de cette garantie doit avoir fait preuve en Suisse d'un comportement irréprochable (<ref-ruling> consid. 3c p. 5, 22 consid. 4a p. 25; sur cette notion, voir arrêts 2A.240/2006 du 20 juillet 2006 consid. 3.2 et 2A.423/2005 du 25 octobre 2005 consid. 4.3 et les arrêts cités). 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êt 2C_723/2008 du 24 novembre 2008, consid. 4.1).
3.2 En l'espèce, le Tribunal cantonal a retenu à juste titre que le recourant n'avait pas fait beaucoup d'efforts pour améliorer sa situation professionnelle et financière qui est obérée (22 poursuites pour un montant de 39'197 fr. 30 au 26 juin 2007). Sans activité lucrative depuis le 30 avril 2005, il a vécu des prestations de l'assurance chômage et du revenu d'insertion. Sa mission temporaire de trois mois et son activité accessoire dans un night club ne permettent pas non plus de considérer qu'il bénéficie d'un travail stable qui lui permettrait de rembourser ses dettes. Dans cette situation, sa fille ne doit pas s'attendre à recevoir un soutien financier de son père. Celui-ci ne conteste d'ailleurs pas qu'il ne s'est jamais acquitté de la pension alimentaire due à sa fille, qu'il s'était engagé à verser lors de l'audience du Tribunal civil du district de La Chaux-de-Fonds du 29 janvier 2007, et qu'à ce titre, il était débiteur de l'Etat de Neuchâtel d'un montant de 10'300 fr. au 4 mai 2009. Comme la relevé le Tribunal cantonal, il existe dès lors un risque sérieux qu'il tombe durablement et dans une large mesure à l'assistance publique au sens de l'art. 10 al. 1 let. d LSEE.
A cela s'ajoute ses condamnations pénales ne sauraient être considérées comme étant toutes de peu de gravité, en particulier celles des 19 novembre 2002 et 3 mai 2006, où il a chaque fois été condamné à un mois d'emprisonnement, notamment pour vol. Même si les cinq autres condamnations qui ont suivi étaient de moindre gravité, le comportement du recourant démontre clairement qu'il a de grandes difficulté à s'adapter à l'ordre établi (art. 10 al. 1 let. b LSEE). L'arrêt attaqué retient du reste que le recourant ne cesse d'enfreindre l'ordre public.
Dans ces circonstances, il existe un intérêt public prépondérant à éloigner le recourant de Suisse et le droit de visite qu'il exerce sur sa fille ne suffit pas pour permettre le renouvellement de son autorisation de séjour sur la base de l'art. 8 CEDH. Il apparaît au demeurant que ce droit de visite n'est pas exceptionnel et qu'il devrait pouvoir être organisé depuis l'étranger dans le cadre de séjours touristiques, au besoin en aménageant les modalités de ce droit quant à sa fréquence et sa durée (arrêt 2C_80/2007 du 25 juillet 2007, consid. 2.2). Autorisé à séjourner en Suisse depuis mars 2003, alors qu'il avait 28 ans et demi, le recourant n'aura en effet aucune difficulté à se réintégrer dans son pays d'origine, où il a conservé toutes ses attaches.
Pour le reste, le fait de vivre avec une ressortissante suisse, alors qu'il n'a pas réussi à démontrer que son divorce et son remariage étaient imminents, ne lui donne pas le droit de se prévaloir de l'art. 8 § 1 CEDH.
3.3 Au vu de ce qui précède, le Tribunal cantonal n'a pas violé le droit fédéral, ni abusé de son pouvoir d'appréciation en considérant que les conditions pour renouveler l'autorisation de séjour du recourant n'étaient pas remplies. Le recours doit dès lors être rejeté.
4. Les conclusions du recours devant le Tribunal fédéral étaient clairement vouées à l'échec, de sorte que la demande d'assistance judiciaire doit être rejetée (<ref-law>). Le recourant supportera donc les frais judiciaires (art. 65 et 66 LTF), étant précisé que ceux-ci seront fixés en tenant compte de sa situation financière (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté.
2. La demande d'assistance judiciaire est rejetée.
3. Les frais judiciaires, arrêtés à 800 fr., sont mis à la charge du recourant.
4. Le présent arrêt est communiqué au mandataire du recourant, au Service de la population et à la Cour de droit administratif et public du Tribunal cantonal du canton de Vaud, ainsi qu'à l'Office fédéral des migrations.
Lausanne, le 4 février 2010
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: La Greffière:
Müller Rochat