Faits:
A. Ressortissant algérien né en 1986, X._ est arrivé en Suisse le 22 mars 1997 avec sa soeur et a été mis au bénéfice d'une autorisation de séjour en vertu du regroupement familial avec son père. Sa mère est restée en Algérie.
X._ n'a acquis aucun métier et ne peut se prévaloir d'aucune intégration socio-professionnelle. Depuis septembre 2005, il est à la charge des services sociaux.
B. Sur le plan pénal, X._ a fait l'objet de nombreuses condamnations prononcées par les autorités judiciaires vaudoises.
Alors qu'il était mineur, il a été condamné à :
- 9 jours de détention pour vol, dommage à la propriété, violation de domicile, contravention à la loi fédérale sur les stupéfiants (LStup) selon jugement du 7 mars 2002;
- 15 jours de détention pour brigandage et contravention à la LStup selon jugement du 9 juillet 2002;
- 5 mois de détention pour lésions corporelles simples et simples qualifiées, vol, complicité de vol, brigandage, dommage à la propriété, recel, injure, contrainte, violence ou menaces contre les autorités et les fonctionnaires, infraction à la loi fédérale sur les armes, infraction et contravention à la LStup, ainsi que contravention à la loi fédérale sur les transports publics selon jugement du 7 décembre 2004.
Une fois majeur, il a été condamné à :
- 12 mois d'emprisonnement pour rixe, agression et complicité de crime manqué de vol et contravention à la LStup par jugement du 14 avril 2005 pour des faits commis le 26 juillet 2004;
- 3 mois d'emprisonnement pour voies de fait, vol, dommages à la propriété et menaces, par ordonnance rendue le 1er mai 2006 pour des faits commis en décembre 2005;
- 10 jours d'emprisonnement et 300 fr. d'amende pour violation de la loi fédérale sur la circulation routière et contravention à la LStup, par ordonnance du 30 octobre 2006 pour des faits commis en juin 2006;
- 480 heures de travail d'intérêt général pour remise à des enfants de substances nocives, vol, actes d'ordre sexuel avec des enfants, infraction et contravention à la LStup, selon jugement du 10 mars 2008, pour des faits commis le 11 septembre 2006;
- 200 heures de travail d'intérêt général pour lésions corporelles simples et rixe commises en avril 2006, selon jugement du 11 mars 2008 (les jours de travail d'intérêt général ont été convertis ultérieurement en 180 jours d'emprisonnement);
- 18 mois d'emprisonnement sous déduction de 240 jours de détention avant jugement, peine partiellement complémentaire à celles prononcées les 10 et 11 mars 2008, pour agression, vol et contravention à la LStup, selon jugement du 19 février 2009, confirmé par la Cour de cassation pénale du Tribunal cantonal vaudois du 3 avril 2009, pour des faits survenus entre mars et juin 2008.
C. Par décision du 10 août 2006, le Service de la population du canton de Vaud (ci-après le Service cantonal) a refusé le renouvellement de l'autorisation de séjour de l'intéressé et lui a enjoint de quitter le territoire cantonal sans délai. Cette décision est devenue définitive et exécutoire.
Le 16 février 2007, X._ a déposé une demande de réexamen, en faisant valoir son prochain mariage avec une Suissesse et sa présence dans le cadre d'une instruction pénale.
Par décision du 22 avril 2008, devenue définitive et exécutoire, le Service cantonal a refusé de lui délivrer une autorisation de séjour en vue de mariage et lui a imparti un délai d'un mois pour quitter le territoire vaudois.
D. Après l'avoir informé préalablement et lui avoir donné le droit de se prononcer, le Service cantonal, par décision du 27 février 2009, a prononcé le renvoi de Suisse de X._, sans délai, dès qu'il aurait satisfait à la justice vaudoise.
Par arrêt du 9 septembre 2009, le Tribunal cantonal vaudois a rejeté le recours de X._ et confirmé la décision du Service cantonal du 27 février 2009.
E. Contre l'arrêt du 9 septembre 2009, X._ dépose un recours constitutionnel subsidiaire, respectivement un recours en matière de droit public. Dénonçant une violation de son droit d'être entendu, ainsi que des art. 3 et 8 CEDH, il conclut à l'annulation de cette décision et requiert l'assistance judiciaire.
Par ordonnance du 21 octobre 2009, le Président de la IIe Cour de droit public a admis la demande d'effet suspensif présentée par X._.
Le Service cantonal a renoncé à se déterminer sur le recours; le Tribunal cantonal s'est pour sa part référé à son arrêt et a conclu au rejet du recours.

Considérant en droit:
1. La loi fédérale sur les étrangers est entrée en vigueur le 1er janvier 2008 (RO 2007 5487). En vertu de l'art. 126 al. 1 LEtr, les demandes déposées avant cette date sont régies par l'ancien droit. Par analogie avec cette disposition, la jurisprudence applique également l'ancien droit à toutes les procédures initiées d'office en première instance avant le 1er janvier 2008 (cf. arrêt 2C_329/2009 du 14 septembre 2009 consid. 2.1). Le litige a pour objet le renvoi du recourant. Cette procédure a été entamée par le Service cantonal après le prononcé de la décision du 22 avril 2008 refusant de délivrer au recourant une autorisation de séjour. La présente cause est par conséquent régie par la loi sur les étrangers.
2.1 L'arrêt attaqué porte exclusivement sur le renvoi du recourant, prononcé en application de l'art. 66 LEtr. En vertu de l'art. 83 let. c ch. 4 in fine LTF, le recours en matière de droit public est irrecevable contre les décisions concernant le renvoi. Par conséquent, cette voie de droit n'est pas ouverte contre une décision fondée, comme en l'espèce, sur l'art. 66 LEtr (THOMAS HÄBERLI, in Basler Kommentar, Bundesgerichtsgesetz, 2008, no 107 ad <ref-law>). En revanche, dans la mesure où une autorité cantonale a statué en dernière instance, la décision de renvoi peut être attaquée par la voie du recours constitutionnel subsidiaire (cf. arrêt 2D_49/2008 du 9 juillet 2008).
Le mémoire du recourant ne sera donc examiné que dans la mesure où il remplit les exigences de recevabilité propres à un recours constitutionnel subsidiaire. Si tel est le cas, le fait que le recourant ait aussi qualifié son écriture, de manière erronée, de recours en matière de droit public, ne saurait lui nuire (cf. <ref-ruling> consid. 1.2 p. 382 et les arrêts cités).
2.2 Déposé dans le délai prescrit (cf. art. 100 al. 1 et 117 LTF), le recours a été interjeté à l'encontre d'une décision finale (cf. art. 90 et 117 LTF), rendue par une autorité cantonale supérieure de dernière instance (cf. art. 86 al. 1 let. d et al. 2 et <ref-law>).
2.3 Selon l'<ref-law>, la qualité pour former un recours constitutionnel subsidiaire suppose d'avoir pris part à la procédure devant l'autorité précédente ou d'avoir été privé de la possibilité de le faire (let. a) et d'avoir un intérêt juridique à l'annulation ou à la modification de la décision attaquée (let. b). La notion d'intérêt juridique correspond à celle d'intérêt juridiquement protégé au sens de l'ancien art. 88 OJ, qui était exigé pour former un recours de droit public (<ref-ruling> consid. 3 et 5). Par analogie avec la jurisprudence rendue sous l'ancienne loi fédérale d'organisation judiciaire (cf. arrêt 2P.143/2003 du 19 décembre 2003 consid. 1.1, in ZBl 105/2004 p. 212; arrêt 2P.199/1995 du 22 novembre 1996 consid. 1b/aa), il y a donc lieu de reconnaître au recourant un intérêt juridique au sens de l'<ref-law> lui permettant de recourir à l'encontre de la décision de renvoi (cf. YVES DONZALLAZ, Loi sur le Tribunal fédéral, 2008, no 2808). La question de l'intérêt actuel ne se pose pas en l'occurrence, dès lors que le recourant est encore en Suisse, du fait que sa requête d'effet suspensif a été admise (cf. arrêt 2P.143/2003 précité consid. 1.2).
Le recours, envisagé comme un recours constitutionnel subsidiaire, est donc en principe recevable.
2.4 Il convient toutefois de rappeler que la présente procédure ne concerne que le renvoi du recourant. La décision attaquée n'a pas les caractéristiques d'un prononcé sur le fond, mais seulement d'une décision d'exécution (cf. ANDREAS ZÜND/LADINA ARQUINT HILL, Beendingung der Anwesenheit, Entfernung und Fernhaltung, in Ausländerrecht, 2e éd., 2009, no 8.61). Le recourant ne peut donc dans ce cadre faire valoir des griefs reposant sur un droit de séjourner en Suisse, ni remettre en cause le refus de lui octroyer une autorisation de séjour (cf. ALAIN WURZBURGER, Commentaire de la LTF, 2009, p. 780 no 58 ad <ref-law>). Du reste, deux décisions, entrées en force, lui ont refusé une telle autorisation respectivement le 10 août 2006 et le 22 avril 2008. Dans la mesure où le recourant se prévaut d'un véritable droit à séjourner en Suisse, son recours est irrecevable.
3. Le recours constitutionnel ne peut être exercé que pour violation des droits constitutionnels (<ref-law>). Le Tribunal fédéral n'examine que les griefs soulevés et motivés de façon détaillée par la partie recourante (art. 106 al. 2 et 117 LTF; <ref-ruling> consid. 3.2 p. 88; <ref-ruling> consid. 2.2 p. 246; <ref-ruling> consid. 3.2 p. 444). Il statue sur la base des faits constatés dans la décision attaquée; il ne peut rectifier ou compléter que les constatations de fait auxquelles l'autorité précédente est parvenue en violation des droits constitutionnels (<ref-law>; <ref-ruling> consid. 7.1 p. 398).
4. Dénonçant une violation de l'art. 29 al. 2 Cst., le recourant reproche aux juges cantonaux d'avoir refusé de donner suite à sa requête tendant à la mise en oeuvre d'une expertise psychiatrique aux fins de déterminer les risques que représenterait pour lui un retour en Algérie.
4.1 Le droit d'être entendu, tel qu'il est garanti à l'art. 29 al. 2 Cst., comprend notamment le droit pour l'intéressé d'obtenir qu'il soit donné suite à ses offres de preuve pertinentes (<ref-ruling> consid. 3 p. 157; <ref-ruling> consid. 2.2 p. 505). Le juge est cependant autorisé à effectuer une appréciation anticipée des preuves déjà disponibles et, s'il peut admettre de façon exempte d'arbitraire qu'une preuve supplémentaire offerte par une partie serait impropre à ébranler sa conviction, refuser d'administrer cette preuve (<ref-ruling> consid. 3 p. 157; <ref-ruling> consid. 2.1 p. 428; en ce qui concerne le refus d'une expertise, cf. arrêt 2C_724/2008 du 16 février 2009 consid. 3.3).
4.2 En l'espèce, le Tribunal cantonal avait à disposition, pour évaluer l'état psychique du recourant, un rapport d'expertise psychiatrique du CHUV du 29 février 2008, ainsi qu'un courrier du psychologue et du médecin de l'unité de médecine pénitentiaire du Centre hospitalier du Chablais du 8 juillet 2009. Ces deux documents, dont le recourant ne prétend pas que la teneur et les extraits auraient été arbitrairement retranscrits dans l'arrêt attaqué, décrivent de manière précise les troubles du comportement dont souffre l'intéressé. Les juges cantonaux ont d'ailleurs admis sur cette base que l'état de fragilité psychique du recourant nécessitait des soins. Le recourant confond l'évaluation de son état de santé psychique avec le point de savoir si un traitement peut être dispensé en Algérie. Or, ce dernier aspect ne relève pas d'une expertise psychiatrique, mais de l'appréciation des circonstances locales. Partant, les juges pouvaient sans arbitraire estimer être suffisamment renseignés sur l'état psychique du recourant, sans devoir encore procéder à une nouvelle expertise médicale. On ne discerne donc aucune violation de l'art. 29 al. 2 Cst.
5. Dans la mesure où le recourant se prévaut de l'art. 8 CEDH, son grief est irrecevable. Comme déjà indiqué, le droit pour le recourant d'obtenir une autorisation de séjour a déjà été définitivement tranché par deux décisions entrées en force; il ne peut donc se prévaloir d'un droit découlant de l'art. 8 CEDH lui permettant de séjourner en Suisse dans le cadre de la présente procédure, qui porte exclusivement sur son renvoi (cf. supra consid. 2.4; voir aussi arrêt 2P.199/1995 du 22 novembre 1996 consid. 1b/bb). Au demeurant, âgé de plus de 18 ans, ne vivant ni avec son père ni avec sa soeur et n'étant pas marié, le recourant ne pourrait de toute manière rien tirer de l'art. 8 CEDH, dès lors qu'il ne fait valoir aucun élément de dépendance particulier avec sa famille (cf. <ref-ruling> consid. 5; arrêt 2A.51/2006 du 8 mai 2006 consid. 4.2.4).
6. Reste à examiner si, comme le soutient le recourant, son renvoi viole l'art. 3 CEDH.
6.1 L'art. 3 CEDH prohibe notamment les traitements inhumains ou dégradants. Pour tomber sous le coup de cette disposition, un mauvais traitement doit atteindre un minimum de gravité. L'appréciation de ce minimum dépend de l'ensemble des données de la cause (<ref-ruling> consid. 3.2.1). Selon la jurisprudence de la Cour européenne des droits de l'homme concernant le défaut de traitement médical approprié dans le pays de renvoi, ce n'est que dans des situations exceptionnelles, en raison de "considérations humanitaires impérieuses", que la mise à exécution d'une décision d'éloignement d'un étranger peut emporter violation de l'article 3 CEDH (arrêt CourEDH Emre contre Suisse du 22 mai 2008 § 88). Les étrangers qui sont sous le coup d'un arrêté d'expulsion ne peuvent en principe revendiquer le droit de rester sur le territoire d'un État contractant afin de continuer à y bénéficier de l'assistance médicale. Ainsi, le fait que la situation d'une personne dans son pays d'origine serait moins favorable que celle dont elle jouit dans le pays d'accueil n'est pas déterminant du point de vue de l'article 3 CEDH (arrêt Emre § 91). Il faut des motifs sérieux et avérés de croire que l'intéressé, si on l'expulse vers le pays de destination, y courra un risque réel d'être soumis à un traitement contraire à l'art. 3 CEDH (arrêt CourEDH N. contre Royaume-Uni du 27 mai 2008 § 30). La Cour européenne des droits de l'homme exige un seuil de gravité élevé pour que l'état de santé d'une personne lui permette de s'opposer à son expulsion (arrêt Emre § 92; arrêt N. c/ Royaume-Uni § 42 ainsi que § 32 ss énumérant la jurisprudence de la Cour relative à l'art. 3 et à l'expulsion de personnes gravement malades).
6.2 En l'espèce, il ressort de l'arrêt attaqué que le recourant souffre d'un trouble de la personnalité et présente une fragilité psychique, de sorte qu'un soutien thérapeutique lui serait bénéfique. Selon l'expertise psychiatrique, ces troubles ont notamment pour origine le fait que le recourant a souffert de la séparation d'avec sa mère, restée en Algérie. En Suisse, il n'a jamais réussi à s'intégrer et à s'adapter à la société, alors qu'il reconnaît avoir eu une enfance très heureuse en Algérie où il a suivi sa scolarité sans problème. Selon les psychiatres, son éloignement de sa mère, restée en Algérie, lui pèse. Le recourant a du reste effectué dans ce pays en 2003 un séjour de trois mois, qui s'est bien déroulé. En outre, les juges sont partis de l'idée que le recourant pourrait être suivi pour ses troubles en Algérie, pays qui abrite de nombreux centres hospitaliers universitaires, dont un hôpital psychiatrique à Alger, ville située à 80 km de Medea, où réside la mère du recourant et qui bénéfice d'un hôpital régional. Sur la base des constatations cantonales, on ne se trouve ainsi à l'évidence pas dans une situation exceptionnelle entraînant une violation de l'art. 3 CEDH.
6.3 Dans sa motivation, le recourant s'écarte des faits retenus dans l'arrêt attaqué, opposant sa propre appréciation à celle du Tribunal cantonal, mais sans invoquer à cet égard de violation de droits constitutionnels, notamment de l'interdiction de l'arbitraire. Partant, la Cour de céans ne peut tenir compte des éléments invoqués par le recourant (cf. art. 116 et 118 LTF). Au demeurant, le recourant méconnaît le caractère strict de la jurisprudence de la Cour européenne des droits de l'homme, dès lors que les faits qu'il invoque (précarité de son environnement social en Algérie, simple probabilité de ne pas recevoir de traitement et absence de réseau familial) - fussent-ils avérés - ne révèlent pas l'existence d'un cas exceptionnel justifiant, sous l'angle de l'art. 3 CEDH, de renoncer à son renvoi.
Dans ces circonstances, le recours ne peut qu'être rejeté dans la mesure de sa recevabilité.
7. Au vu de ce qui précède, les conclusions du recourant apparaissent dénuées de toute chance de succès, de sorte que la requête d'assistance judiciaire doit être rejetée (cf. <ref-law>). Des frais de justice seront donc mis à la charge du recourant (cf. <ref-law>), mais ils seront fixés en tenant compte de sa situation (cf. <ref-law>). Il ne sera pas alloué de dépens (cf. <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 à 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: Le Greffier:
Müller Vianin