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.