Faits:
A. Y._, ressortissant camérounais né en 1979, est arrivé en Suisse en juin 2003 et y a déposé une demande d'asile dans le canton de Berne. L'Office fédéral des réfugiés n'est pas entré en matière sur sa demande et a ordonné son renvoi par décision du 6 octobre 2003, confirmée sur recours le 27 octobre suivant. L'intéressé n'a pas obtempéré à l'ordre de renvoi et est resté en Suisse. Entre le 3 juin 2004 et le 12 juillet 2010, il a fait l'objet de quatre condamnations à des peines allant de 200 fr. d'amende pour la moins grave à 120 jours de privation de liberté pour la plus grave, principalement pour des infractions à la législation fédérale sur les étrangers. Il a purgé sa peine du 6 janvier au 6 mai 2011.
Deux mois avant d'entrer en détention, le 4 octobre 2010, Y._ a déposé une demande d'autorisation de séjour dans le canton de Vaud en vue de se marier avec A.X._, une ressortissante camerounaise née en 1966, titulaire d'une autorisation de séjour; à l'époque, cette dernière, mère de cinq enfants, était séparée depuis plusieurs années de B.X._, un citoyen suisse qu'elle avait épousé en janvier 2003 et avec lequel elle était en instance de divorce; elle vivait depuis 2008 en compagnie de Y._ et de trois de ses enfants, à savoir: Junior, un enfant de nationalité camerounaise né en 1995 dans son pays d'origine, ainsi que deux enfants qu'elle avait eus pendant son mariage avec B.X._, A._ et B._, nés respectivement en 2003 et en 2009. Le 22 novembre 2010, Y._ a reconnu ce dernier enfant comme sa fille après qu'une procédure en désaveu de paternité eut constaté, en juillet 2010, que B.X._ n'en était pas le père.
En décembre 2010, saisi une première fois d'une demande de mariage de Y._ et de A.X._, l'officier d'état civil a refusé d'ouvrir la procédure préparatoire, car le divorce de la prénommée, prononcé le 2 décembre 2010, ne devait être exécutoire, en l'absence de recours, au plus tôt qu'en janvier de l'année suivante - ce qui fut le cas. Les intéressés ont déposé une nouvelle demande de mariage le 6 mars 2011; en réponse à cette requête, l'officier d'état civil a fixé aux fiancés, le 8 mars 2011, un délai de "60 jours non prolongeables" pour déposer une pièce prouvant la légalité du séjour en Suisse de Y._, conformément à l'<ref-law>, sous peine "de non-entrée en matière sur la procédure de mariage."
Par décision du 11 mars 2011, le Service de la population du canton de Vaud (ci-après: le Service cantonal) n'est pas entré en matière sur la demande d'autorisation de séjour déposée par Y._ en octobre 2010, eu égard au principe de l'exclusivité de la procédure d'asile, et a invité l'intéressé à quitter le canton de Vaud pour celui de Berne.
B. Y._ et A.X._ ont recouru contre la décision précitée auprès du Tribunal cantonal du canton de Vaud, Cour de droit administratif et public (ci-après: le Tribunal cantonal), en concluant à la délivrance "d'une autorisation de séjour avec activité lucrative" en faveur du prénommé, subsidiairement à l'octroi d'une telle autorisation "jusqu'au lendemain de la célébration de son mariage." A titre de mesures provisoires, ils demandaient que Y._ fût autorisé à résider et à exercer une activité lucrative dans le canton de Vaud jusqu'à droit connu sur leur recours. Ils estimaient que le refus d'autorisation de séjour opposé à l'intéressé violait le droit au mariage garanti à l'art. 12 CEDH.
Par arrêt du 21 avril 2011, le Tribunal cantonal a rejeté le recours. Pour l'essentiel, il a considéré qu'une exception au principe de l'exclusivité de la procédure d'asile ne pouvait être admise que si un droit à une autorisation de séjour était manifeste, ce qui n'était pas le cas en l'espèce, au vu des démarches restant à accomplir en vue d'un mariage en Suisse; par ailleurs, il a estimé qu'il n'était pas compétent pour se prononcer sur la conformité du principe précité avec la garantie du droit au mariage prévu à l'art. 12 CEDH, en précisant également que l'application de l'<ref-law> sortait de l'objet de la contestation.
C. Par écriture du 4 mai 2011, Y._ et A.X._ forment un "recours" au Tribunal fédéral contre l'arrêt précité. En bref, ils soutiennent, comme en procédure cantonale, que le refus de leur accorder une autorisation de séjour, au moins pendant le temps nécessaire pour préparer et célébrer leur mariage, constitue une violation du droit au mariage garanti à l'art. 12 CEDH. Ils concluent à l'annulation de l'arrêt attaqué et à l'octroi "d'une autorisation de séjour avec activité lucrative" en faveur de Y._. Ils demandent par ailleurs le bénéfice de l'assistance judiciaire.
Invité à se déterminer sur la requête d'effet suspensif présentée à l'appui du recours, le Service cantonal a précisé qu'il n'était pas compétent pour exécuter le renvoi de Suisse de l'intéressé, car celui-ci était toujours attribué au canton de Berne en vertu de sa demande d'asile. Le Tribunal cantonal s'en est remis à justice quant à la requête d'effet suspensif et a conclu au rejet du recours sur le fond. L'Office fédéral des migrations n'a pas répondu dans le délai fixé.
Par ordonnance du 1er juin 2011, le Président de la IIe Cour de droit public du Tribunal fédéral a octroyé le bénéfice de l'effet suspensif au recours.

Considérant en droit:
1. Le Tribunal fédéral examine d'office sa compétence (<ref-law>). Il contrôle donc librement la recevabilité des recours déposés devant lui.
1.1 Selon l'art. 14 al. 1 de la loi du 26 juin 1998 sur l'asile (LAsi, RS 142.31), "à moins qu'il n'y ait droit", un requérant d'asile débouté, comme le recourant Y._, ne peut pas engager une procédure visant l'octroi d'une autorisation de séjour avant d'avoir quitté la Suisse (principe dit de l'exclusivité de la procédure d'asile; cf. <ref-ruling> consid. 2.1 p. 202 s.).
En l'espèce, l'arrêt attaqué confirme une décision par laquelle le Service cantonal, faisant application de l'<ref-law>, a refusé d'entrer en matière sur une demande d'autorisation de séjour déposée par Y._ en vue de permettre son mariage avec A.X._. L'objet de la présente contestation ne porte donc pas sur l'octroi ou le refus d'une autorisation de séjour en tant que telle, mais uniquement sur l'existence potentielle d'un droit à une telle autorisation permettant, conformément à l'<ref-law> in initio, de faire exception au principe de l'exclusivité de la procédure d'asile (sur les conditions pour admettre une telle exception, cf. infra consid. 3.1). Partant, les conclusions des recourants sont irrecevables en tant qu'elles tendent à l'octroi d'une autorisation de séjour; elles doivent être interprétées comme visant à obtenir, outre l'annulation de l'arrêt attaqué, l'ouverture d'une procédure en vue d'une autorisation de séjour (cf. arrêt 2C_551/2008 du 17 novembre 2008 consid. 3.2).
1.2 Les recourants n'ont pas indiqué par quelle voie de recours ils procèdent auprès du Tribunal fédéral. Toutefois, cette imprécision ne saurait leur nuire si le recours remplit les exigences légales de la voie de droit à disposition (au sujet d'une voie erronée de recours, <ref-ruling> consid. 1.2 p. 302/303, 308 consid. 4.1 p. 314). Comme son nom l'indique, le recours constitutionnel subsidiaire n'entre en ligne de compte que si la décision attaquée ne peut pas faire l'objet d'un autre recours au Tribunal fédéral (cf. <ref-law>); il convient dès lors en premier lieu d'examiner si la voie du recours en matière de droit public prévue aux <ref-law> est ouverte.
1.3 Aux termes de l'art. 83 let. c ch. 2 LTF, le recours en matière de droit public est irrecevable à l'encontre des décisions en matière de droit des étrangers qui concernent une autorisation à laquelle ni le droit fédéral ni le droit international ne donnent droit. A cet égard, il suffit que le recourant démontre de manière soutenable l'existence d'un droit potentiel à une autorisation de séjour pour que son recours soit recevable; le point de savoir si toutes les conditions sont effectivement réunies dans un cas particulier relève de l'examen au fond (<ref-ruling> consid. 1.1 p. 179).
En l'espèce, l'arrêt attaqué retient que l'intéressé ne peut déduire ni de l'art. 8 CEDH, ni de l'art. 12 CEDH, de droit potentiel à une autorisation de séjour, si bien qu'il ne peut pas demander une autorisation de séjour pour se marier avant d'avoir quitté la Suisse en vertu du principe de l'exclusivité de la procédure d'asile. Les recourants contestent cette appréciation, en soutenant que le droit au mariage garanti à l'art. 12 CEDH contraignait le Service cantonal de leur délivrer, même provisoirement, une telle autorisation de séjour en vue de mener à bien leur projet de mariage; au vu de la stabilité de leurs relations et de la sincérité de leur volonté de fonder une communauté conjugale, ils estiment que le refus du Service cantonal confirmé par les premiers juges a violé l'art. 12 CEDH. Cette argumentation n'apparaît pas insoutenable (en ce sens, cf. MARIE-LAURE PAPAUX VAN DELDEN, Le droit au mariage et à la famille: analyse critique des restrictions, in FamPra 2011 p. 589 ss, p. 596; MARC SPESCHA, Autorités de l'état civil: complices d'expulsion pour des motifs de police des étrangers ou garantes du droit au mariage ?, in Revue de l'état civil, 2010, p. 116 ss, p. 120) et suffit à établir l'existence d'un droit potentiel à une autorisation de séjour en faveur de Y._. Le recours échappe dès lors à la clause d'irrecevabilité prévue à l'art. 83 let. c ch. 2 LTF, étant précisé que le point de savoir si un tel droit doit être reconnu en l'espèce relève du fond et non de la recevabilité.
1.4 Pour le surplus, le recours est dirigé contre une décision finale (<ref-law>) rendue dans une cause de droit public (<ref-law>) par une autorité cantonale de dernière instance (art. 86 al. 1 lettre d LTF). En outre, il a été déposé en temps utile (<ref-law>) et en la forme prévue (<ref-law>) par les destinataires de la décision attaquée qui ont un intérêt digne de protection à l'annulation ou à la modification de celle-ci (<ref-law>). Il est donc en principe recevable comme recours en matière de droit public.
2. 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 ceux-ci n'aient été établis de façon manifestement inexacte ou en violation du droit au sens de l'<ref-law> (cf. <ref-law>). En l'espèce, l'arrêt attaqué ne contient aucune constatation concernant la seconde demande de mariage des recourants, bien que ces faits, essentiels pour la compréhension du cas, aient été allégués et prouvés en procédure cantonale; il y a dès lors lieu de compléter d'office l'état de fait cantonal sur ce point (cf. supra ad lettre A, 3ème paragraphe).
3. 3.1 Selon la jurisprudence, une exception au principe de l'exclusivité de la procédure d'asile n'est admise que si le droit à une autorisation de séjour requis par l'<ref-law> in initio apparaît "manifeste" (cf. arrêts 2C_493/2010 du 16 novembre 2010 consid. 1.4; 2C_733/2008 du 12 mars 2009 consid. 5.1). Tel n'est en principe pas le cas si le requérant invoque uniquement le droit à la protection de sa vie privée au sens de l'art. 8 § 1 CEDH, car la reconnaissance d'un droit à une autorisation de séjour par ce biais revêt un caractère exceptionnel (cf. arrêt 2C_493/2010 du 16 novembre 2010 consid. 1.4). En revanche, la jurisprudence admet que l'art. 8 § 1 CEDH justifie de faire exception à l'<ref-law> lorsqu'il en va de la protection de la vie privée et familiale, notamment pour protéger les relations entre époux (cf. arrêt 2C_551/2008 du 17 novembre 2008 consid. 4). Une telle exception suppose toutefois, outre l'existence d'une relation étroite et effective entre les époux, que le requérant soit marié avec une personne disposant d'un droit de présence assuré ("ein gefestigtes Anwesenheitsrecht") en Suisse; tel est le cas si son époux jouit de la nationalité suisse ou d'une autorisation d'établissement (cf. <ref-ruling> consid. 1.3.1 p. 145 s.; <ref-ruling> consid. 3.1 p. 285) voire, dans certaines circonstances particulières, d'une simple autorisation de séjour, s'il apparaît d'emblée et clairement que cette autorisation sera durablement prolongée à l'avenir, par exemple pour des motifs d'ordre humanitaire (cf. arrêt précité 2C_551/2008 du 17 novembre 2008 consid. 4).
En l'espèce, il ressort des constatations cantonales que les recourants vivent sous le même toit depuis 2007 (depuis janvier 2007 selon leurs allégués) et qu'ils sont père et mère d'une petite fille qu'ils élèvent ensemble depuis sa naissance en juillet 2008; par ailleurs, même si elle n'a qu'une simple autorisation de séjour, la mère dispose d'un droit de présence assuré en Suisse dans la mesure où elle a la garde et l'autorité parentale sur son fils Dimitri, né en février 2003 d'un père suisse dont il a hérité la nationalité (regroupement familial inversé; cf. <ref-ruling> consid. 5.2 p. 287 confirmé in <ref-ruling> consid. 4.2 p. 250 s.); il apparaît donc que Y._ pourrait selon toute vraisemblance se prévaloir d'un droit à une autorisation de séjour fondé sur l'art. 8 § 1 CEDH par exception au principe de l'exclusivité de la procédure d'asile s'il pouvait épouser A.X._, comme les recourants le veulent mais ne le peuvent, en raison de l'absence d'un titre de séjour du fiancé, point qui constitue l'enjeu de la présente procédure.
3.2 La jurisprudence relative au droit et au respect de la vie privée et familiale (art. 8 § 1 CEDH) permet, à certaines conditions, à un célibataire étranger de déduire un droit à une autorisation de séjour en présence d'indices concrets d'un mariage sérieusement voulu et imminent avec une personne ayant le droit de résider durablement en Suisse (cf. arrêts 2C_97/2010 du 4 novembre 2010 consid. 3.1; 2C_25/2010 du 2 novembre 2010, consid. 6.1 et les références citées). Le Tribunal cantonal a toutefois écarté cette éventualité en l'espèce, au motif que le mariage envisagé n'apparaissait pas imminent, la procédure préparatoire n'ayant pu être engagée qu'après l'entrée en force du jugement de divorce des époux X._, en janvier 2011, tandis "que la vérification et l'authentification des documents d'état civil de Y._ pourrait prendre plusieurs mois" (arrêt attaqué, consid. 2b).
3.3 Les recourants ne se prévalent pas de l'art. 8 CEDH, mais invoquent uniquement la garantie du droit au mariage prévue à l'art. 12 CEDH. A leurs yeux, cette garantie a été violée, dans leur cas, par le refus des autorités cantonales, fondé sur l'<ref-law>, d'entrer en matière sur leur demande d'une autorisation de séjour en vue du mariage projeté. A l'appui de leur opinion, ils se réfèrent notamment à l'arrêt rendu par la Cour européenne des droits de l'homme (CourEDH) le 14 décembre 2010 dans la cause O'Donoghue et consorts c./Royaume-Uni, requête no 34848/07.
3.4 Cette affaire concerne le cas d'un ressortissant nigérian et de sa fiancée, double ressortissante britannique et irlandaise, qui avaient été empêchés de se marier au Royaume-Uni de mai 2006 à juillet 2008 en raison de la législation introduite dans ce pays en 2005 pour lutter contre les mariages de complaisance. Cette législation interdisait aux personnes soumises au contrôle de l'immigration de se marier, à moins de disposer d'une autorisation spécialement délivrée à cet effet lors de leur entrée au Royaume-Uni ou d'obtenir par la suite un "Certificate of Approval" contre le paiement d'un montant de 295 £; mais seuls les étrangers légalement entrés au Royaume-Uni ou titulaires d'une autorisation de séjour d'une certaine durée pouvaient recevoir un tel certificat; deux modifications de la loi, en 2006 et 2007, ont assoupli le système en permettant aux autres étrangers d'obtenir un "Certificate of Approval" à la condition de fournir des informations supplémentaires prouvant la sincérité de leur projet de mariage.
La CourEDH a conclu à l'unanimité à la violation du droit au mariage des requérants (art. 12 CEDH) pour la période comprise entre mai 2006, date à laquelle ceux-ci avaient exprimé le souhait de se marier, et le 8 juillet 2008, date de la délivrance du "Certificate of Approval". Les juges ont en effet estimé inadmissible que les requérants, dont l'intention de se marier était sincère et ne visait pas à contourner les lois d'immigration, n'avaient pas pu obtenir le certificat litigieux en raison tout d'abord, jusqu'au 19 juin 2007, date de la seconde modification de la loi, de la situation personnelle du fiancé qui était entré illégalement au Royaume et était dépourvu de titre de séjour, puis, par la suite, faute de disposer des moyens leur permettant de s'acquitter des frais de dossier (cf. arrêt précité, § 82 ss).
3.5 Il découle de l'arrêt O'Donoghue et consorts que le droit au mariage garanti par l'art. 12 CEDH peut également être invoqué par des étrangers résidant illégalement dans un Etat membre. Il n'en va pas différemment de la garantie du droit au mariage inscrite à l'art. 14 Cst., qui appartient en principe à toute personne physique majeure, quelle que soit sa nationalité - y compris les apatrides - ou sa religion (cf. JÖRG PAUL MÜLLER/MARKUS SCHEFER, Grundrechte in der Schweiz, 4ème éd., p. 221; RUTH REUSSER, in Ehrenzeller/Mastronardi/Schweizer/ Vallender, Die schweizerische Bundesverfassung, 2ème éd., no 11 ad Art. 14; JEAN-FRANÇOIS AUBERT/PASCAL MAHON, Petit commentaire de la Constitution fédérale de la Confédération suisse, no 4 ad art. 14). Il s'agit en effet d'un droit de l'homme et non d'un droit du citoyen (cf. ANDREAS AUER/GIORGIO MALINVERNI/MICHEL HOTTELIER, Droit constitutionnel suisse, vol. II, 2ème éd., no 419). Il ressort également de l'arrêt O'Donoghue et consorts les deux principes suivants: premièrement, une interdiction systématique d'accéder au mariage opposée à des étrangers sans titre de séjour est contraire à l'art. 12 CEDH, car les droits fondamentaux garantis par la Convention, comme le droit au mariage, ne peuvent pas être limités par des mesures générales, automatiques et indifférenciées (cf. arrêt précité, § 89); secondement, des mesures destinées à lutter contre les mariages de complaisance ne sont admissibles qu'autant qu'elles sont raisonnables et proportionnées (arrêt précité, § 82 ss) et qu'elles visent à déterminer si l'intention matrimoniale des futurs époux est réelle et sincère, soit repose sur la volonté de fonder une communauté conjugale (arrêt précité § 88); à cet égard, la CourEDH a notamment souligné qu'à la différence du droit au respect de la vie privée et familiale (cf. art. 8 § 2 CEDH), aucune ingérence n'est prévue à l'art. 12 CEDH dans le droit au mariage (arrêt précité, § 84) .
Au vu de ces exigences, il faut admettre que le système mis en place par le législateur suisse peut s'avérer contraire à l'art. 12 CEDH lorsqu'un étranger, bien qu'en situation irrégulière en Suisse, désire néanmoins réellement et sincèrement se marier. En effet, en cas de refus de l'autorité de police des étrangers de régulariser - même temporairement - sa situation, il ne pourra pas, en vertu de l'<ref-law>, entré en vigueur le 1er janvier 2011 (RO 2010 p. 3057), concrétiser son projet en Suisse; ce risque est spécialement marqué pour les requérants d'asile déboutés qui ne peuvent, comme on l'a vu (supra consid. 3.1), obtenir l'ouverture d'une procédure d'autorisation de séjour qu'à des conditions relativement restrictives au regard de l'<ref-law>. La doctrine est d'ailleurs apparemment unanime à considérer qu'un refus automatique et sans discernement de l'accès au mariage à tous les étrangers séjournant illégalement en Suisse serait de nature à violer la garantie du droit au mariage (en ce sens, cf. JÖRG PAUL MÜLLER, Bekämpfung von Scheinehen im Konflikt mit der Ehefreiheit: zur Umsetzung der parlamentarischen Initiative Toni Brunner, in Asyl, 24/09, p. 14 ss; MARTINA CARONI/SIMON SCHÄDLER, Lex Brunner und EMRK, in Asyl 4/11, p. 23 ss; PHILIPPE MEIER/LAURA CARANDO, "Pas de mariage en cas de séjour irrégulier en Suisse ?", in Jusletter du 14 février 2011, p. 9; THOMAS GEISER/MARC BUSSLINGER, in Uebersax/Rudin/Hugi Yar/Geiser [éd], Ausländerrecht, 2ème éd., Zurich 2009, no 14.15 ad § 14; SPESCHA, op. cit., p. 119 s.; PAPAUX VAN DELDEN, op. cit. p. 595 ss; DU MÊME AUTEUR, Commentaire Romand, 2010, no 19 ad <ref-law>; MARIO GERVASONI, Mariage fictifs - Mariages d'étrangers sans permis, in Revue de l'état civil, Berne 2008, p. 142 ss; CESLA AMARELLE/MINH SON NGUYEN/DIEYLA SOW, Chronique de jurisprudence relative au droit des étrangers, in PJA 2011, p. 687), du moins lorsque le fiancé a la nationalité suisse ou dispose d'un droit de présence assuré en Suisse (cf. REUSSER, op. cit., no 16). Une telle pratique reviendrait en effet à présumer de manière irréfragable qu'un étranger démuni d'un titre de séjour en Suisse ne peut avoir qu'une volonté viciée de se marier, sans égard à la durée et à la stabilité de sa relation et aux éventuels enfants nés de celle-ci; elle amènerait donc à interdire de manière générale, automatique et indifférenciée l'exercice du droit au mariage pour toute une catégorie de personnes (cf. MEIER/CARANDO, op. cit., p. 4; MÜLLER, op. cit., p. 16). Par ailleurs, on ne saurait considérer que la possibilité pour les fiancés de se marier à l'étranger suffit à remplir les exigences découlant de l'art. 12 CEDH (cf. MEIER/CARANDO, op. cit., p. 5; PAPAUX VAN DELDEN, Commentaire Romand, no 19 ad <ref-law>), car les Etats membres doivent assurer le respect des droits garantis par la Convention sur leur territoire; par ailleurs, une telle possibilité s'apparente à un obstacle important au mariage en raison du temps et des coûts qu'elle entraîne pour les personnes concernées, surtout pour les moins aisées d'entre elles (cf. SPESCHA, op. cit., p. 119 s.).
3.6 Le législateur n'a pas ignoré ces problèmes en édictant l'<ref-law>.
Cette disposition trouve son origine dans une initiative parlementaire intitulée "Empêcher les mariages fictifs", déposée le 16 décembre 2005 par le Conseiller national Toni Brunner (objet no 05.463), qui estimait que l'<ref-law>, introduit le 1er janvier 2008 pour combattre les abus liés à la législation sur les étrangers, ne permettait pas d'empêcher "à coup sûr" les mariages fictifs, car elle laissait aux services de l'état civil une certaine marge d'appréciation sans leur offrir de base légale claire sur laquelle fonder un refus; en inscrivant dans le Code civil l'obligation de démontrer la légitimité du séjour en Suisse, cette lacune serait donc comblée de manière simple et efficace selon l'auteur de l'initiative, et l'on empêcherait les requérants d'asile définitivement déboutés et les personnes séjournant illégalement en Suisse de se soustraire par le mariage à l'obligation de quitter le pays (cf. le texte de l'initiative disponible sur internet à l'adresse http://www.parlament.ch).
Cette initiative a donné lieu à un projet de la loi élaboré par la Commission des institutions politiques du Conseil national (CIP-CN). Selon ce projet, baptisé "Empêcher les mariages en cas de séjour irrégulier", l'<ref-law> entend mettre un terme à l'automatisme consistant, aussitôt qu'un étranger en situation illégale dépose une demande de mariage, à lui délivrer une autorisation de séjour, en tout cas pour la durée de la procédure préparatoire; une telle réforme permet en outre d'harmoniser et de coordonner les décisions de l'état civil et des autorités de police des étrangers (cf. rapport de la CIP-CN du 31 janvier 2008 sur l'initiative parlementaire "Empêcher les mariages fictifs", in FF 2008 2247, p. 2252).
Le Conseil fédéral a estimé, dans la ligne des observations contenues dans le rapport que la CIP-CN lui a remis (cf. pp. 2254 et 2256 du rapport précité), que le système mis en place était conforme à la Constitution fédérale et à la Convention européenne des droits de l'homme sous réserve toutefois, conformément aux principes généraux valables en cas de restriction à des droits fondamentaux, de veiller à ce que l'application des mesures envisagées ne conduise pas dans un cas concret à vider les garanties du mariage (art. 14 Cst.; 12 CEDH) et du respect de la vie privée et familiale (art. 13 Cst.; art. 8 CEDH) de leur substance ou à constituer de fait un obstacle prohibitif à la conclusion du mariage (avis du Conseil du 14 mars 2008 sur l'initiative parlementaire "Empêcher les mariages fictifs", in FF 2008 2261 p. 2263). A cet égard, la CIP-CN a notamment exprimé ce qui suit (rapport précité, p. 2254):
"Les personnes qui séjournent en Suisse de manière illégale et qui souhaitent se marier doivent préalablement demander à régulariser leur séjour. Ces personnes doivent en principe séjourner à l'étranger durant le traitement de leur requête. Des exceptions sont toutefois possibles si les conditions d'admission après le mariage sont manifestement remplies et qu'il n'y a aucun indice que l'étranger entend invoquer abusivement les règles sur le regroupement familial (cf. art. 17 LEtr, par analogie). Afin de respecter le principe de la proportionnalité et d'éviter tout formalisme excessif, les autorités pourront fixer un délai de départ à l'étranger, délai dans lequel le mariage devra cas échéant être célébré et le séjour en Suisse réglé. Ici aussi, les autorités doivent prendre en compte le droit constitutionnel au mariage (art. 14 Cst.) et le droit au respect de la vie privée et familiale (art. 8 CEDH)."
3.7 Cela étant, l'<ref-law> n'offre aucune marge de manoeuvre à l'officier d'état civil confronté à une demande de mariage émanant d'un étranger qui n'a pas établi la légalité de son séjour en Suisse. Celui-ci n'a pas d'autre alternative, conformément au voeu du législateur, que de refuser la célébration du mariage (cf. art. 67 al. 3 de l'ordonnance du 21 avril 2004 sur l'état civil [OEC, RS 211.112.2]). Ainsi, dans le cas d'espèce, en refusant d'entrer en matière sur la demande de mariage des recourants, l'officier d'état civil n'a fait que tirer les conséquences de la décision du Service cantonal rejetant la demande de Y._ d'ouvrir une procédure tendant à la délivrance d'une autorisation de séjour - même provisoire - en vue de préparer et de célébrer son mariage. En ce sens, l'autorité civile est liée par la décision de la police des étrangers. Il appartient ainsi à cette dernière autorité lors de la procédure d'autorisation de séjour en vue du mariage - et non à l'officier d'état civil - de prendre en compte dans sa décision les exigences liées au respect du droit au mariage et au principe de proportionnalité. C'est ainsi qu'il faut comprendre l'appel du législateur, à l'adresse des "autorités" (cf. supra consid. 3.6 dernier paragraphe), à faire preuve de discernement lorsque l'illégalité du séjour de l'un des fiancés en Suisse est de nature à empêcher la célébration du mariage et à porter atteinte à la substance du droit au mariage ou à constituer un obstacle prohibitif à ce droit.
Par conséquent, dans la perspective d'une application de la loi conforme à la Constitution (art. 14 Cst.) et au droit conventionnel (art. 12 CEDH), les autorités de police des étrangers sont tenues de délivrer un titre de séjour en vue du mariage lorsqu'il n'y a pas d'indice que l'étranger entende, par cet acte, invoquer abusivement les règles sur le regroupement familial, et qu'il apparaît clairement que l'intéressé remplira les conditions d'une admission en Suisse après son union (cf. art. 17 al. 2 LEtr par analogie). Dans un tel cas, il serait en effet disproportionné d'exiger de l'étranger qu'il rentre dans son pays pour s'y marier ou pour y engager à distance une procédure en vue d'obtenir le droit de revenir en Suisse pour se marier. En revanche, dans le cas inverse, soit si, en raison des circonstances, notamment de la situation personnelle de l'étranger, il apparaît d'emblée que ce dernier ne pourra pas, même une fois marié, être admis à séjourner en Suisse, l'autorité de police des étrangers pourra renoncer à lui délivrer une autorisation de séjour provisoire en vue du mariage; il n'y a en effet pas de raison de lui permettre de prolonger son séjour en Suisse pour s'y marier alors qu'il ne pourra de toute façon pas, par la suite, y vivre avec sa famille. Cette restriction correspond à la volonté du législateur de briser l'automatisme qui a pu exister, dans le passé, entre l'introduction d'une demande de mariage et l'obtention d'une autorisation de séjour pour préparer et célébrer le mariage.
3.8 Lorsque, comme en l'espèce, l'étranger qui désire se marier est un requérant d'asile (débouté), le principe de l'exclusivité de la procédure d'asile ne saurait, lorsque les conditions d'une application par analogie de l'art. 17 al. 2 LEtr sont réunies, empêcher l'ouverture d'une procédure d'autorisation de séjour en vue du mariage. Contrairement à ce que suggèrent les premiers juges, l'art. 190 Cst. n'interdit nullement une telle interprétation de l'<ref-law>. D'une part, l'exigence jurisprudentielle qu'il existe un droit "manifeste" à une autorisation de séjour pour faire échec au principe de l'exclusivité de la procédure d'asile se concilie tout à fait avec les conditions, de même nature, permettant à un étranger d'attendre l'issue d'une procédure en Suisse en vertu de l'art. 17 al. 2 LEtr. D'autre part, le législateur a clairement manifesté, comme on l'a vu (supra consid. 3.6), sa volonté de faire en sorte que l'introduction de l'<ref-law> ne conduise pas à des violations du droit constitutionnel ou conventionnel (cf. MÜLLER, op. cit., p. 15).
3.9 En l'espèce, au vu des constatations cantonales (cf. supra consid. 3.1), il faut admettre, en l'absence d'éléments contraires au dossier, que la relation des recourants est sérieuse et stable (vie commune depuis 2007; enfant commun depuis juillet 2008) et que leur volonté de se marier est réelle et sincère. Y._ devrait donc, une fois marié, pouvoir obtenir une autorisation de séjour sur la base de l'art. 8 § 1 CEDH en vertu du droit de présence durable de sa future épouse (cf. supra consid. 3.1).
Certes Y._ a un casier judiciaire. Ses deux plus graves condamnations résultent toutefois d'infractions à la loi fédérale sur les étrangers pour séjour illégal en Suisse et consistent en des peines de 90 jours-amende à 15 fr. par jour (avec sursis mais celui-ci a ensuite été révoqué) plus 1'000 fr. d'amende et de finalement 120 jours de privation de liberté. Pour le reste, il a été condamné à des amendes de 400 fr. et 200 fr. pour respectivement s'être opposé à des actes de l'autorité en refusant de décliner son identité à un contrôleur et avoir menacé un autre contrôleur dans le cadre de contrôles des billets de transport public en villes de Berne et de Burgdorf. Dans l'ensemble, ces délits ne sont pas suffisamment graves pour faire apparaître leur auteur comme une personne présentant une menace à l'ordre et à la sécurité publics propre à justifier d'emblée un refus d'autorisation de séjour fondé sur l'art. 8 § 1 CEDH (cf., sous l'angle de l'art. 17 al. 2 LEtr, les arrêts 2C_483/2009 du 18 septembre 2009 consid. 4.2 et 2C_35/2009 du 13 février 2009 consid. 6.5).
Quant à la situation économique de l'intéressé et du couple, l'arrêt ne contient aucune constatation sur ces points. Des allégués des recourants, il apparaît que Y._ ne travaille pas et que A.X._ toucherait une aide sociale pour compléter son salaire d'aide-soignante occupée à 50 % dans une institution pour personnes handicapées. Il est certain que si, après son mariage, l'intéressé devait ne pas travailler et dépendre lui-même de l'aide sociale, il s'exposerait à ne plus recevoir d'autorisation de séjour (cf. art. 44 let. c LEtr). Le danger qu'il émarge concrètement à l'aide sociale, une fois en possession d'un permis de séjour, ne doit toutefois pas s'examiner à la seule lumière de la situation actuelle; il faut également tenir compte de l'évolution probable de celle-ci (cf. <ref-ruling> consid. 3c p. 8; <ref-ruling> consid. 3b p. 6; arrêt 2C_268/2011 du 22 juillet 2011 consid. 6.2.3); or, sur ce point, on peut convenir avec le recourant que sa situation actuelle précaire devrait pouvoir notablement s'améliorer une fois qu'il aura reçu une autorisation de séjour lui permettant de trouver un travail, étant précisé qu'il est encore jeune et apparemment en bonne santé.
On ajoutera que, dans la pesée des intérêts à effectuer sur la base de l'art. 8 § 2 CEDH, l'autorité doit tenir compte de l'intérêt privé à ce que Y._ puisse rester en Suisse non seulement par rapport à sa (future) épouse, mais également à l'égard de sa fille, encore en bas âge, avec laquelle il vit et entretient, selon ses allégués, des liens étroits depuis sa naissance.
Dans ces conditions, il faut admettre que, prima facie, Y._ réunit toutes les conditions pour obtenir une autorisation de séjour en cas de mariage. Le Service cantonal ne pouvait dès lors pas refuser d'entrer en matière sur sa demande d'autorisation de séjour en vue de se marier. Il convient donc d'annuler l'arrêt attaqué et de renvoyer le dossier à cette autorité pour qu'elle entre en matière et rende une décision sur le droit de Y._ à une autorisation de séjour - éventuellement temporaire - pour pouvoir se marier.
4. Il suit de ce qui précède que le recours doit être admis et l'arrêt attaqué annulé, la cause étant renvoyée au Service cantonal pour qu'il rende une nouvelle décision au sens des considérants.
Il n'est pas prélevé de frais de justice. Obtenant gain de cause, les recourants ont droit, solidairement entre eux, à une indemnité à titre de dépens à la charge du canton de Vaud (cf. art. 68 al. 1, 2 et 5 en lien avec l'<ref-law>) incluant un montant pour la procédure cantonale (cf. <ref-law>). Avec ce prononcé, la demande d'assistance judiciaire est sans objet.

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est admis dans la mesure où il est recevable. L'arrêt attaqué est annulé et la cause renvoyée au Service de la population du canton de Vaud pour nouvelle décision au sens des considérants.
2. Il n'est pas perçu de frais judiciaires.
3. Le canton de Vaud versera aux recourants, créanciers solidaires, un montant de 4'000 fr. à titre de dépens pour la procédure fédérale et cantonale.
4. Le présent arrêt est communiqué au mandataire des recourants, 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 23 novembre 2011
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: Zünd
Le Greffier: Addy