Faits:
A. X._, ressortissant de Serbie et Monténégro, né en 1973, est entré en Suisse au mois d'octobre 1998 et y a déposé une demande d'asile, qui a été définitivement rejetée par décision de la Commission fédérale de recours en matière d'asile (actuellement Tribunal administratif fédéral) du 26 juillet 2000.
Le 25 août 2000, X._ a épousé à Monthey, en Valais, une ressortissante suisse, Y._, née en 1959. Il a obtenu, sur recours, une autorisation de séjour pour regroupement familial, le 25 avril 2002. Par ordonnance de mesures protectrices de l'union conjugale du 1er juin 2004, les époux ont été autorisés à vivre séparés dès le 21 avril 2004, pour une durée indéterminée. Ils n'ont ensuite jamais repris la vie commune.
B. X._ est arrivé dans le canton de Vaud en juin 2004 et y a obtenu une autorisation de séjour et de travail, le 25 novembre 2004.
Le 17 mai 2005, X.Y._ a indiqué au Service cantonal vaudois de la population qu'elle attendait les résultats de la procédure pénale engagée contre son mari pour voies de fait, menaces et viol d'une femme, avec laquelle ce dernier avait entretenu une liaison, avant de décider si la reprise de la vie commune était envisageable.
Après le dépôt de la demande de renouvellement de l'autorisation de séjour de l'intéressé, le 2 mars 2007, le Service de la population a procédé à une enquête sur la situation matrimoniale des époux. Il est notamment ressorti de l'audition de X.Y._ du 24 juillet 2007 qu'elle n'avait plus de contacts avec son mari depuis le début du mois de février 2006 et qu'auparavant, elle le rencontrait occasionnellement pour aller boire un verre. Le 11 octobre 2007, elle a précisé que les époux n'avaient plus habité ensemble depuis leur mariage, qu'elle avait été trompée dès le début par son mari qui ne s'était jamais intéressé à elle comme un être humain, mais uniquement comme une porte d'entrée à son établissement en Suisse. Quant à X._, il a déclaré, le 10 septembre 2007, être toujours amoureux de son épouse, avoir des contacts téléphoniques réguliers avec elle et aller souvent manger chez elle.
Par décision du 18 juin 2008, le Service de la population a refusé la prolongation de l'autorisation de séjour de X._.
Le Tribunal cantonal vaudois (Cour de droit administratif et public), a été saisi d'un recours contre cette décision. Durant l'instruction, il a reçu la dernière audition de X.Y._ du 20 août 2008, laquelle a déclaré que son mari s'était de nouveau approché d'elle depuis le mois de juin 2008, qu'il lui téléphonait régulièrement et lui laissait même des mots doux à la porte. Le Tribunal a également obtenu l'ordonnance de non-lieu, rendue le 16 avril 2009 par le Juge d'instruction du Bas-Valais dans la procédure pénale menée contre X._, ainsi que plusieurs certificats médicaux, dont le dernier au sujet d'un accident de travail survenu le 2 septembre 2008.
Statuant par voie de circulation, le Tribunal cantonal a rejeté le recours, par arrêt du 12 août 2009.
C. Agissant par la voie du recours en matière de droit public, X._ conclut, avec suite de frais et dépens, à l'annulation de l'arrêt cantonal du 12 août 2009 et à l'octroi d'une autorisation de séjour. Le recourant demande également à ê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 du 11 septembre 2009, la demande d'effet suspensif contenue dans le recours a été admise, par le Président de la IIe Cour de droit public du Tribunal fédéral.
Le 16 septembre 2009, l'Etat civil de Sion a communiqué que le jugement de divorce des époux X.Y._, prononcé par le Tribunal des districts de Martigny et de St-Maurice, était entré en force le 3 septembre 2009.
Le 30 novembre 2009, le mandataire du recourant a encore produit un échange de correspondances entre le recourant et son ex-épouse.

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 2 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.
2.2 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).
En l'espèce, le Tribunal cantonal a statué avant que le divorce des époux X.Y._, devenu définitif le 3 septembre 2009, ne soit prononcé. Même si, en principe, 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>), ce divorce constitue un fait nouveau que le Tribunal fédéral peut exceptionnellement pendre en considération pour examiner la recevabilité du recours (<ref-ruling> consid. 1.1.3 p. 149; arrêt 2C_591/2008 du 24 novembre 2008 consid. 2.2). Tel n'est en revanche pas le cas des correspondances entre les époux produites le 30 novembre 2009, qui constituent des pièces nouvelles au sens de l'<ref-law> et doivent ainsi être écartées.
2.3 N'étant plus marié à une Suissesse, le recourant ne peut fonder son droit à recourir sur l'existence d'un mariage formel (art. 7 al. 1 1ère phrase LSEE). Toutefois, il est constant que les époux X.Y._ ont été mariés pendant neuf ans, de sorte que le recourant peut en principe prétendre à l'octroi d'une autorisation d'établissement fondée sur un séjour régulier et ininterrompu de cinq ans (art. 7 al. 1 2ème phrase LSEE). La question de savoir s'il y a abus de droit à se prévaloir de la durée du mariage pour obtenir le droit de séjourner en Suisse et si cet abus existait déjà avant l'écoulement du délai de cinq ans est en effet une question de droit et non de recevabilité (<ref-ruling> consid. 1.1.5 p. 150).
2.4 Il y a lieu dès lors d'entrer en matière sur le recours qui remplit les autres conditions de recevabilité du recours en matière de droit public (<ref-law>).
3. 3.1 Saisi d'un recours en matière de droit public, le Tribunal fédéral examine librement la violation du droit fédéral, qui comprend les droits de nature constitutionnelle (cf. art. 95 lettre a et 106 al. 1 LTF), sous réserve des exigences de motivation figurant à l'<ref-law>. Il y procède en se fondant sur les faits constatés par l'autorité précédente (cf. <ref-law>), à moins que ces faits n'aient été établis de façon manifestement inexacte ou en violation du droit au sens de l'<ref-law> (cf. <ref-law>). Le recourant doit expliquer de manière circonstanciée en quoi les conditions d'une exception prévue par l'<ref-law> seraient réalisées, faute de quoi il n'est pas possible de tenir compte d'un état de fait qui diverge de celui qui est contenu dans l'acte attaqué. En particulier, l'autorité de céans n'entre pas en matière sur des critiques de type appellatoire portant sur l'état de fait ou sur l'appréciation des preuves (cf. <ref-ruling> consid. 5.2.2 p. 322; <ref-ruling> consid 1.4 p. 400, 133 II 249 consid. 1.4 p. 254/255).
3.2 Le recourant a sollicité l'édition du dossier de la procédure de divorce, qui s'est déroulée auprès du Tribunal des districts de Martigny et de St-Maurice, afin de prouver que c'était bien son ex-épouse et non lui qui avait souhaité divorcer, contrairement à ce que le Tribunal cantonal a retenu. Cette réquisition n'est pas admissible (<ref-law>). Au demeurant, les motifs de la rupture de l'union conjugale ne sont pas déterminants (<ref-ruling> consid. 4.2 p. 117), de sorte qu'il n'est pas nécessaire de savoir lequel des époux est à l'origine de la demande de divorce.
Le recourant a également requis l'édition par l'Office du Juge d'instruction du Bas-Valais du dossier pénal P109 499 concernant la plainte/ dénonciation à l'encontre de la personne responsable de son accident de travail du 2 septembre 2008. Cette réquisition doit également être rejetée, du moment que ce dossier porte sur une question qui n'est pas litigieuse devant le Tribunal fédéral.
4. Sur le fond, le Tribunal cantonal a pris en considération le comportement du recourant vis-à-vis de son épouse depuis l'obtention de son permis de séjour, le 25 avril 2002, et en a déduit que l'union conjugale était vidée de toute substance bien avant l'échéance du délai de cinq ans de l'art. 7 al. 1 LSEE. Le recourant lui reproche, en substance de n'avoir tenu compte que des déclarations de son épouse, alors que lui-même avait pris contact avec sa femme, l'avait rencontrée à plusieurs reprises, chez elle et au restaurant, et avait accepté le divorce uniquement parce que celui-ci avait été demandé par son épouse.
4.1 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). L'existence d'un éventuel abus de droit à invoquer le bénéfice de l'art. 7 al. 1 LSEE doit être appréciée avec retenue et n'être admise que restrictivement; seul l'abus manifeste d'un droit doit être sanctionné (<ref-ruling> consid. 4a p. 103). En particulier, on ne saurait déduire du simple fait que les époux ne vivent pas (ou plus) ensemble l'existence d'un abus de droit, le législateur ayant volontairement renoncé, à l'art. 7 al. 1 LSEE, à faire dépendre le droit à une autorisation de séjour de la vie commune (<ref-ruling> consid. 3 p. 149 ss). En revanche, il y a abus de droit, selon la jurisprudence, lorsque le conjoint étranger invoque un mariage n'ayant qu'une existence formelle dans le seul but d'obtenir une autorisation de séjour, car ce but n'est pas protégé par l'art. 7 al. 1 LSEE (<ref-ruling> consid. 4.2 p. 267 et les arrêts cités). Le mariage n'existe plus que formellement lorsque l'union conjugale est rompue définitivement, c'est-à-dire lorsqu'il n'y a plus d'espoir de réconciliation; les causes et les motifs de la rupture ne jouent pas de rôle (<ref-ruling> consid. 4.2 p. 117 et les arrêts cités). L'absence de cohabitation pendant une période significative constitue aussi un indice permettant de dire que les époux ne veulent plus mener une véritable vie conjugale (<ref-ruling> consid. 10.3 p. 136).
4.2 Il est en l'espèce constant que les époux vivent séparés, en tous cas depuis la séparation de corps autorisée judiciairement dès le 21 avril 2004. Si les conjoints ont eu des échanges par la suite, il semble que ceux-ci se sont surtout intensifiés depuis le mois de juin 2008, après que le recourant avait reçu la décision de non-renouvellement de son autorisation de séjour par le Service de la population, ce qui impliquait son renvoi de Suisse. Quoi qu'il en soit, même si les rencontres provoquées par le recourant n'étaient pas entretenues uniquement pour les besoins de la cause, force est de constater que les critiques qu'il formule à l'encontre de l'arrêt attaqué sont, à cet égard, purement appellatoires. Rien ne permet en effet de douter des déclarations de l'épouse, depuis son courrier du 17 mai 2005 à sa dernière audition d'août 2008, d'où il ressort clairement que le recourant ne s'est pas préoccupé d'elle pendant son mariage, qu'il l'a trompée et laissée seule dans l'appartement conjugal, qu'en raison de cette situation, elle avait rencontré d'importants problèmes de santé et qu'une éventuelle réconciliation n'était pas envisageable. A cela s'ajoute qu'en neuf ans de mariage, les époux n'ont jamais eu de projet commun et n'ont pas davantage tenté sérieusement de se réconcilier depuis leur séparation d'avril 2004.
4.3 Dans ces circonstances, les premiers juge n'ont pas violé le droit fédéral, ni abusé de leur pourvoir d'appréciation, en retenant que la rupture de l'union conjugale était effective avant l'échéance du délai de cinq ans de l'art. 7 al. 1 LSEE. Ils pouvaient ainsi retenir que le recourant commettait un abus de droit en se prévalant de la durée de son mariage pour obtenir le renouvellement de son autorisation de séjour ou une autorisation d'établissement.
5. Le recourant reproche aussi au Tribunal cantonal d'avoir violé son droit d'être entendu en refusant sa comparution personnelle et l'audition de son épouse, ce qui l'aurait empêché de fournir la preuve de la fausseté des affirmations de cette dernière.
Le droit d'être entendu, tel qu'il est garanti par l'art. 29 al. 2 Cst., ne comprend pas le droit d'être entendu oralement, ni celui d'obtenir l'audition de témoins. L'autorité peut en effet mettre un terme à l'instruction lorsque les preuves administrées lui ont permis de forger sa conviction et que, procédant d'une manière non arbitraire à une appréciation anticipée des preuves qui lui sont encore proposées, elle a la certitude que ces dernières ne pourraient l'amener à modifier son opinion (<ref-ruling> consid. 5.3 p. 148; <ref-ruling> consid. 2.1 p. 428/429 et la jurisprudence citée).
En l'occurrence, le Tribunal cantonal a estimé sans arbitraire qu'il disposait de tous les éléments nécessaires pour résoudre les questions soulevées par le présent litige. Les conditions pour renoncer à entendre le recourant et son ex-épouse étaient en effet pleinement remplies, dès lors que, comme on l'a vu (supra consid. 4), les premiers juges pouvaient avoir la conviction qu'une reprise de la vie commune n'était pas envisageable et que les causes et les motifs de la rupture de l'union conjugale ne jouent pas de rôle dans l'appréciation de l'abus de droit (<ref-ruling> consid. 4.2 p. 117 et les arrêts cités).
Le grief tiré de la violation du droit d'être entendu se révèle ainsi infondé et doit être rejeté.
6. Au surplus, il faut constater qu'en sa qualité de ressortissant de Serbie et Monténégro, le recourant ne peut pas non plus se prévaloir d'une autre disposition issue du droit fédéral ou du droit international. Quant à une éventuelle autorisation pour cas de rigueur, elle ne relève pas de la compétence du Tribunal fédéral (cf. art. 83 let. c ch. 5 LTF). Partant, le recours est irrecevable en tant qu'il porte sur l'examen auquel a procédé l'autorité cantonale à ce titre, en vertu de l'art. 4 LSEE.
7. La demande d'assistance judiciaire contenue dans le recours doit être rejetée, dès lors que les conclusions du recours étaient clairement vouées à l'échec au sens de l'<ref-law>. Les frais judiciaires doivent ainsi être mis à la charge du recourant (<ref-law>).

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, au Service de la population, au Tribunal cantonal du canton de Vaud, Cour de droit administratif et public, et à l'Office fédéral des migrations.
Lausanne, le 22 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