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. 