Faits:
A. A.a O._, ressortissant africain né en 1963, est entré illégalement en Suisse en février 2005. Il suit un traitement médical en raison d'une maladie grave. Le 17 octobre 2007, le Service de la population du canton de Vaud l'a informé du fait qu'il était disposé à lui délivrer une autorisation de séjour « hors contingent » en raison de son état de santé. Il a toutefois réservé l'approbation de l'Office fédéral des migrations. Le 9 janvier 2009, il lui a délivré une attestation selon laquelle il était légitimé à séjourner dans le canton de Vaud jusqu'à droit connu sur la décision de police des étrangers, mais au plus pour une durée de six mois.
Par décision du 18 juillet suivant, l'Office fédéral des migrations a refusé de mettre O._ au bénéfice d'une exception aux mesures de limitation du nombre des étrangers prévues par l'Ordonnance limitant le nombre des étrangers, du 6 octobre 1986 (cf. art. 13 let. f OLE; aujourd'hui abrogée; RO 1986 1791, 2007 5528); il lui a imparti un délai au 31 octobre 2009 pour quitter le territoire suisse. L'intéressé a recouru devant le Tribunal administratif fédéral.
A.b O._ a perçu des prestations d'aide sociale dès le 1er mai 2005, notamment un revenu d'insertion (RI) depuis le 1er janvier 2006. Par décision du 19 décembre 2008, le Centre social régional de Lausanne (ci-après : CSR) a mis fin à cette prestation, avec effet dès le 31 mars 2009, en précisant que dès cette date, seule une aide d'urgence serait allouée. Le 7 septembre 2009, le Service de prévoyance et d'aide sociales du canton de Vaud (SPAS) a rejeté le recours interjeté contre cette décision par O._.
B. Ce dernier a déféré la cause au Tribunal cantonal vaudois, qui a rejeté le recours par jugement du 21 octobre 2009.
C. O._ interjette un recours en matière de droit public contre ce jugement, en concluant formellement à la constatation de la violation de diverses dispositions de la Constitution du canton de Vaud (Cst.-VD) et de la Convention européenne des droits de l'homme (CEDH). Il a demandé que l'effet suspensif soit attribué au recours.
Le SPAS a conclu au rejet du recours et s'en est remis à justice en ce qui concerne l'octroi de l'effet suspensif au recours. Le CSR s'est référé au jugement entrepris et ne s'est pas opposé à l'octroi de l'effet suspensif. Le Service de la population a renoncé à se déterminer.
D. Par ordonnance du 11 janvier 2010, le juge délégué à l'instruction de la cause a attribué l'effet suspensif au recours.

Considérant en droit:
1. 1.1 La voie du recours en matière de droit public est ouverte en l'espèce. Le recours est en effet dirigé contre un jugement final (<ref-law>) rendu dans une cause de droit public (<ref-law>) par une autorité cantonale de dernière instance (art. 86 al. 1 let. d LTF), sans que l'on se trouve dans l'un des cas d'exception mentionnés par l'<ref-law>.
1.2 Des conclusions uniquement constatatoires sont en principe irrecevables, faute d'intérêt digne de protection au recours, lorsque le recourant peut obtenir en sa faveur un jugement condamnatoire ou formateur; en ce sens, le droit d'obtenir un jugement en constatation de droit est subsidiaire (cf. <ref-ruling> consid. 4 p. 122; <ref-ruling> consid. 2.1 p. 19; <ref-ruling> consid. 2.1 p. 290; <ref-ruling> consid. 1b p. 24).
1.3 Le recourant a conclu formellement à la constatation de la violation de diverses dispositions de la Convention européenne des droits de l'homme et de la Constitution du canton de Vaud. Il ressort néanmoins de l'ensemble du mémoire de recours (cf. <ref-ruling> consid. 4 cité; <ref-ruling> consid. 2 p. 135; FLORENCE AUBRY GIRARDIN, in Commentaire de la LTF, 2009, no 18 ad art. 42; LAURENT MERZ, in Commentaire bâlois, Bundesgerichtsgesetz, 2008, no 18 ad art. 42) que le recourant souhaite en réalité obtenir le maintien de son droit à l'aide sociale, sans réduction à l'aide d'urgence. Il convient d'interpréter ses conclusions dans ce sens et d'entrer en matière sur le recours.
2. 2.1 La loi sur l'action sociale vaudoise, du 2 décembre 2003 (LASV; RSV 850.051), s'applique aux personnes domiciliées ou en séjour dans le canton (art. 4 al. 1 LASV). Elle ne s'applique pas aux personnes visées par la loi sur l'aide aux requérants d'asile et à certaines catégories d'étrangers, du 7 mars 2006 (LARA; RSV 142.21), à l'exception des dispositions relatives à l'aide d'urgence (art. 4 al. 2 LASV). Sont notamment concernées par cette exclusion les personnes séjournant illégalement sur territoire vaudois (art. 2 al. 1 ch. 4 LARA).
2.2 Aux termes de l'art. 4a LASV, l'aide d'urgence est dans la mesure du possible allouée sous forme de prestations en nature. Elle comprend en principe le logement, en règle générale, dans un lieu d'hébergement collectif (a), la remise de denrées alimentaires et d'articles d'hygiène (b), les soins médicaux d'urgence dispensés en principe par la Clinique X._, en collaboration avec les Hospices cantonaux/Z._ (c), ainsi que l'octroi, en cas de besoin établi, d'autres prestations de première nécessité (d).
3. 3.1 Les premiers juges considèrent que le séjour du recourant en Suisse est illicite au sens de l'art. 2 al. 1 ch. 4 LARA, même s'il est au bénéfice d'une tolérance de la part des autorités vaudoises. Le recourant ne peut donc pas prétendre aux prestations prévues par la LASV, exceptée l'aide d'urgence.
3.2 Le recourant soulève les griefs de violation des art. 11, 12, 15, 33 et 38 Cst.-VD, ainsi que des art. 3 et 8 CEDH. Il soutient que l'interprétation et l'application des normes cantonales en matière d'aide sociale et d'aide d'urgence par les premiers juges, en particulier les art. 4 LASV et 2 LARA, sont incompatibles avec les normes constitutionnelles et internationales invoquées. Il est notamment contradictoire de « tolérer » le séjour du recourant sur le territoire vaudois tout en qualifiant ce séjour d'illégal et en niant, pour ce motif, le droit à des prestations d'aide sociale plus étendues que l'aide d'urgence. Le recourant se réfère, dans ce contexte, à une ordonnance du Tribunal administratif fédéral du 10 septembre 2009 constatant l'effet suspensif du recours interjeté contre la décision de l'Office fédéral des migrations du 18 juillet 2009. Enfin, il fait valoir que l'aide d'urgence allouée par les autorités ne comprend qu'un hébergement insuffisant au vu des garanties relatives à la liberté personnelle et au droit de toute personne au respect de sa vie privée et familiale, de son domicile et de sa correspondance; une atteinte à ces libertés n'est pas nécessaire en l'espèce, dès lors que les autorités pourraient y mettre fin en statuant dans un délai raisonnable sur la demande d'autorisation de séjour.
4. Aux termes de l'art. 12 de la Constitution fédérale, quiconque est dans une situation de détresse et n'est pas en mesure de subvenir à son entretien a le droit d'être aidé et assisté, et de recevoir les moyens indispensables pour mener une existence conforme à la dignité humaine. Le recourant ne soutient pas que l'art. 33 Cst.-VD, auquel il se réfère, aurait une portée plus large, de sorte que la jurisprudence relative à l'art. 12 Cst. est pertinente pour trancher le litige.
Selon cette jurisprudence, le droit fondamental à des conditions minimales d'existence ne garantit pas un revenu minimum, mais uniquement la couverture des besoins élémentaires pour survivre d'une manière conforme aux exigences de la dignité humaine, tels que la nourriture, le logement, l'habillement et les soins médicaux de base. L'art. 12 Cst. se limite, autrement dit, à ce qui est nécessaire pour assurer une survie décente afin de ne pas être abandonné à la rue et réduit à la mendicité (cf. <ref-ruling> consid. 5.3 p. 123; <ref-ruling> consid. 6.1 p. 261; <ref-ruling> consid. 3.1 p. 172; <ref-ruling> consid. 4.1 p. 74; <ref-ruling> consid. 2c p. 373). Sa mise en oeuvre peut être différenciée selon le statut de la personne assistée. Ainsi la jurisprudence a-t-elle admis, pour les personnes qui doivent quitter la Suisse, en particulier les requérants d'asile sous le coup d'une décision de non-entrée en matière, qu'il n'y a pas lieu de poursuivre un intérêt d'intégration ou de garantir des contacts sociaux durables, compte tenu du caractère en principe temporaire de leur présence sur le territoire suisse (ATF <ref-ruling> consid. 8.2 p. 182).
5. 5.1 Dans un ATF 8C_724/2009 du 11 juin 2010 (consid. 4), le Tribunal fédéral a considéré que celui qui réside illégalement en Suisse et qui dépose une demande de régularisation en raison d'une situation personnelle d'extrême gravité ne dispose pas d'un véritable titre de séjour en Suisse pendant la durée de la procédure, à moins de s'être vu expressément délivrer une autorisation provisoire par l'autorité cantonale compétente. Même en l'absence d'une décision de renvoi exécutoire, les autorités cantonales peuvent donc, en principe, réduire les prestations d'aide sociale allouées à la personne concernée et les limiter à une aide présentant un caractère transitoire marqué, comme l'aide d'urgence garantie au terme d'une décision de non-entrée en matière ou de rejet d'une demande d'asile au sens de l'art. 82 al. 1 et 2 LAsi, sans violer l'art. 12 Cst. ni l'art. 33 Cst.-VD. Par ailleurs, le fait de qualifier le séjour d'illégal au sens de l'art. 2 al. 1 ch. 4 LARA ne constitue pas une interprétation ou une application arbitraire, ni contraire aux règles de la bonne foi, de cette disposition (cf. art. 11 Cst.-VD, 5 al. 3 et 9 Cst.; ATF 8C_724/2009 cité, consid. 5).
5.2 Le Service de la population a délivré, le 9 janvier 2009, une attestation dans laquelle il précise que O._ est légitimé à séjourner dans le canton de Vaud jusqu'à droit connu sur son autorisation de séjour, mais au maximum pendant une durée de six mois. Il n'est pas certain que la portée d'une telle attestation se limite à celle d'une simple tolérance et que ce document ne constitue pas un titre de séjour excluant, provisoirement tout au moins, l'application de l'art. 2 al. 1 ch. 4 LARA. Il convient toutefois de laisser la question ouverte, dès lors que le recourant a de toute façon bénéficié du revenu d'insertion litigieux pendant la durée de validité de l'attestation en cause, en raison de l'effet suspensif de ses recours successifs. Pour la période postérieure à sa durée de validité, l'attestation n'a pas été renouvelée, de sorte que la jurisprudence exposée au consid. 5.1 ci-avant est applicable. En l'occurrence, les autorités cantonales peuvent donc, en principe, réduire les prestations allouées au recourant et les limiter à l'aide d'urgence. Le fait que la décision de renvoi prononcée par l'Office fédéral des migrations le 18 juillet 2009 n'est pas exécutoire, en raison de l'effet suspensif du recours interjeté devant le Tribunal administratif, n'est pas déterminant dans ce contexte, sans qu'il soit nécessaire de trancher le point de savoir s'il s'agit ou non d'un fait nouveau au sens de l'<ref-law>.
5.3 L'art. 4a al. 3 let. a LASV prévoit « en règle générale », un hébergement collectif pour les personnes au bénéfice de l'aide d'urgence. Comme cela ressort des discussions parlementaires à l'occasion de l'adoption de cette disposition, celle-ci est formulée de manière relativement ouverte; il s'agit en effet de laisser une marge d'appréciation à l'autorité d'exécution pour statuer dans des cas particuliers, notamment pour les familles ou les personnes atteintes dans leur santé, lorsque la situation de détresse perdure (cf. Bulletin des séances du Grand Conseil du canton de Vaud no 68, séance du 14 février 2006, p. 8184, 8187, 8189; voir également ATF 8C_724/2009 cité, consid. 6). En l'occurrence, l'Etablissement vaudois pour l'accueil des migrants (EVAM) dispose donc encore d'une marge d'appréciation, après la décision de suppression du revenu d'insertion du 19 décembre 2008, pour déterminer le logement qui sera attribué à au recourant au titre de l'aide d'urgence. Les griefs de violation des art. 8 CEDH, 12 et 15 Cst.-VD, en relation avec les conditions de son hébergement, en particulier dans le contexte d'une procédure d'autorisation de séjour durant depuis plusieurs années, sont donc prématurés. Au demeurant, on observera que si la procédure en matière de droit des étrangers est effectivement pendante depuis plusieurs années, la décision administrative à l'origine du présent litige ne prévoyait de limiter les prestations allouées au recourant qu'à partir du 1er avril 2009. Cette décision n'a pas encore pris effet en raison de l'effet suspensif attribué aux recours successifs de l'intéressé.
5.4 En relation avec le grief de violation des art. 3 CEDH et 12 al. 3 Cst.-VD relatifs à l'interdiction de toute peine ou tout traitement inhumain ou dégradant, le recourant n'expose pas en quoi la limitation à l'aide d'urgence des prestations qui lui sont allouées pendant la procédure d'examen de sa demande de régularisation constituerait un tel traitement. A défaut de motivation suffisante - la seule référence à une situation « schizophrénique » dans laquelle il serait placé ainsi qu'aux motifs médicaux invoqués à l'appui de sa demande de régularisation ne constitue pas une telle motivation -, il n'y a pas lieu d'entrer en matière sur ce grief. Par ailleurs, le grief de violation de l'art. 38 Cst.-VD, également soulevé par le recourant sans développement particulier, ne revêt aucune portée propre par rapport aux autres dispositions constitutionnelles auxquelles il se réfère; il convient par conséquent de rejeter le grief, pour autant qu'il soit recevable, pour les motifs déjà exposés en rapport avec ces dispositions.
6. Vu ce qui précède, le recourant voit ses conclusions rejetées et ne peut prétendre de dépens (<ref-law>). Il a déposé une demande d'assistance judiciaire en vue d'être dispensé d'avancer les frais de justice. Dès lors que le recours n'était pas dénué de chances de succès et que l'indigence du recourant est établie (<ref-law>), il convient d'accepter cette requête. Le recourant est toutefois rendu attentif au fait qu'il devra rembourser la caisse du Tribunal s'il se trouve ultérieurement en mesure de le faire (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté.
2. L'assistance judiciaire est accordée au recourant.
3. Les frais judiciaires, arrêtés à 300 fr., sont mis à la charge du recourant. Ils sont toutefois supportés provisoirement par la caisse du Tribunal.
4. Le présent arrêt est communiqué aux parties, au Centre social régional de Lausanne, au Service de la population et au Tribunal cantonal vaudois.
Lucerne, le 18 juin 2010
Au nom de la Ire Cour de droit social
du Tribunal fédéral suisse
Le Président: Le Greffier:
Ursprung Métral