Faits :
A.
A._ est un ressortissant camerounais né en 1979, selon les informations figurant au dossier. Le 10 novembre 2014, il est entré en Suisse sans être au bénéfice d'un visa.
En février 2015, il a fait la connaissance de B._, ressortissante suisse née en 1960. Le 1er juin 2015, le couple a déposé une demande de procédure préparatoire de mariage auprès de l'Office d'état civil de Lausanne. Les fiancés font ménage commun au domicile de l'intéressée, à Ecublens.
Par ordonnance pénale du 3 décembre 2015, A._ a été condamné pour entrée illégale et séjour illégal à une peine de 90 jours-amende à 30 fr. le jour, avec sursis pendant 2 ans, ainsi qu'à une amende de 540 fr. Malgré sa situation illégale, l'intéressé a été mis par le Service de la population du canton de Vaud (ci-après : le Service cantonal) au bénéfice d'une tolérance de séjour pendant la procédure préparatoire de mariage, régulièrement renouvelée pour des durées variables, la dernière fois le 11 octobre 2018 pour une durée d'un mois.
Par décision du 24 juillet 2017, après avoir donné aux fiancés la possibilité d'exercer leur droit d'être entendus, le Département de l'Economie, de l'innovation et du sport du canton de Vaud a déclaré irrecevable la procédure préparatoire de mariage introduite par les intéressés, au motif que les données personnelles et la capacité matrimoniale de A._ n'avaient pas été établies de manière non équivoque et probante. Il avait en effet été constaté que l'intéressé, tout au long de ladite procédure préparatoire, avait produit pas moins de quatre actes de naissance successifs, dont l'authenticité s'était avérée douteuse, dès lors que ceux-ci étaient contradictoires, modifiés, voire antidatés, et qu'aucun éclaircissement exhaustif n'avait été fourni par les fiancés sur de telles irrégularités de forme. Il n'avait par ailleurs pas été établi que l'obtention de pièces convaincantes était impossible ou qu'elle ne pouvait pas être raisonnablement exigée. Cette décision d'irrecevabilité a été confirmé par arrêt du 4 octobre 2018 de la Cour de droit administratif et public du Tribunal cantonal du canton de Vaud (ci-après: le Tribunal cantonal), qui n'a pas fait l'objet d'un recours.
B.
Par décision du 20 novembre 2018, le Service cantonal a refusé d'octroyer à A._ une autorisation de séjour en vue du mariage et a prononcé le renvoi du précité de Suisse, en lui impartissant un délai d'un mois dès la notification de ladite décision pour quitter le pays.
Le 19 décembre 2018, A._ a recouru contre cette décision auprès du Tribunal cantonal. Il invoquait notamment avoir ouvert, avec sa fiancée, une nouvelle procédure préparatoire de mariage, produisant une lettre du 9 novembre 2018 à teneur de laquelle l'Officier de l'état civil de Lausanne adressait aux fiancés la liste des documents à présenter pour que puissent être effectuées les premières formalités en vue du mariage, tout en informant ceux-ci que leur dossier complet devait lui être impérativement adressé dans un délai de trois mois, soit jusqu'au 9 février 2019, à défaut de quoi la pré-réservation serait annulée.
Par courrier du 13 février 2019, après avoir constaté qu'aucun document propre à établir l'identité de l'intéressé n'avait été produit par ce dernier, qui s'était limité à indiquer que leur obtention était "en cours", la Direction de l'état civil a classé la procédure préparatoire de mariage.
Le 16 mai 2019, A._ a spontanément produit devant le Tribunal cantonal une copie d'un jugement du 8 avril 2019 du Tribunal de Premier Degré de Yaoundé Centre administratif ordonnant notamment la rectification de son acte de naissance, puis, par lettre du 30 octobre 2019, il a spontanément exposé que son conseil au Cameroun "aurait envoyé tous les documents nécessaires au mariage aujourd'hui par la poste".
Par arrêt du 5 novembre 2019, le Tribunal cantonal a rejeté le recours déposé par A._, retenant en substance que le mariage n'était pas imminent et n'apparaissait pas non plus envisageable dans un délai proche, aucune procédure préparatoire de mariage n'étant en cours. En outre, le couple n'élevait pas d'enfant ensemble, si bien que l'intéressé ne pouvait se prévaloir du droit au respect de la vie familiale garanti par l'art. 8 CEDH. Sa situation n'était par ailleurs pas constitutive d'un cas individuel d'extrême gravité.
C.
A._ (ci-après: le recourant 1) et B._ (ci-après: la recourante 2) interjettent un recours en matière de droit public auprès du Tribunal fédéral contre l'arrêt du Tribunal cantonal précité. Ils concluent, outre à l'octroi de l'effet suspensif et de l'assistance judiciaire, principalement, à l'annulation de l'arrêt entrepris et à l'octroi d'une autorisation de séjour en faveur du recourant 1; subsidiairement, à l'annulation de l'arrêt entrepris, à la reconnaissance d'un concubinage stable entre les recourants 1 et 2 et au renvoi de la cause à l'instance inférieure pour nouvelle décision.
Par ordonnance du 21 novembre 2019, le Président de la IIe Cour de droit public du Tribunal fédéral a admis la requête d'effet suspensif. Par correspondance du 12 décembre 2019, le Tribunal fédéral a renoncé provisoirement à exiger une avance de frais et a informé les recourants qu'il serait statué ultérieurement sur l'octroi de l'assistance judiciaire.
Le Tribunal cantonal et le Service cantonal renoncent à se déterminer sur le recours.

Considérant en droit :
1.
Le Tribunal fédéral examine d'office sa compétence (<ref-law>) et contrôle librement la recevabilité des recours qui lui sont soumis (<ref-ruling> consid. 2.1 p. 397; <ref-ruling> consid. 2 p. 59).
1.1. Selon 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. D'après la jurisprudence, il suffit qu'il existe un droit potentiel à l'autorisation, étayé par une motivation soutenable, pour que cette clause d'exclusion ne s'applique pas et que, partant, la voie du recours en matière de droit public soit ouverte. La question de savoir si les conditions d'un tel droit sont effectivement réunies relève du fond (<ref-ruling> consid. 1.1 p. 332 et les arrêts cités).
En l'occurrence, le recourant 1 fait ménage commun avec la recourante 2, de nationalité suisse, depuis 2015. Bien qu'il ne l'exprime pas clairement, on comprend, à la lecture de son recours, qu'il se prévaut, du reste de manière soutenable, de l'art. 8 CEDH pour prétendre demeurer en Suisse auprès de sa fiancée, avec qui il envisage de se marier. Un droit potentiel à l'octroi d'une autorisation de séjour en vue du mariage ne pouvant, sur la base de la relation précitée, être a prioriexclu (cf. arrêts 2C_198/2018 du 25 juin 2018 consid. 1.1; 2C_702/2011 du 23 février 2012 consid. 1.2), son recours échappe au motif d'irrecevabilité prévu à l'art. 83 let. c ch. 2 LTF. Le recours en matière de droit public lui est ainsi ouvert. Il en va de même s'agissant de la recourante 2, sous réserve de ce qui suit.
1.2. Aux termes de l'<ref-law>, a qualité pour former un recours en matière de droit public quiconque a pris part à la procédure devant l'autorité précédente ou a été privé de la possibilité de le faire, est particulièrement atteint par la décision ou l'acte normatif attaqué et a un intérêt digne de protection à son annulation ou à sa modification.
En l'espèce, si la qualité pour recourir du recourant 1, qui est le destinataire de l'arrêt entrepris, est manifestement donnée, tel n'est pas le cas s'agissant de la recourante 2. Cette dernière n'a en effet pas pris part à la procédure de recours devant la dernière instance judiciaire cantonale et n'expose pas avoir été privée de la possibilité de le faire. Elle n'a par conséquent pas qualité pour recourir en son nom contre l'arrêt entrepris. Le recours, s'agissant de la recourante 2, est partant irrecevable sous cet angle.
1.3. Pour le surplus, l'arrêt attaqué est une décision finale (<ref-law>) rendue par un tribunal supérieur de dernière instance cantonale (art. 86 al. 1 let. d et al. 2 LTF) dans une cause de droit public (<ref-law>). Déposé en temps utile (<ref-law>) et dans les formes prescrites (<ref-law>), le recours est partant recevable s'agissant du recourant 1.
2.
2.1. Saisi d'un recours en matière de droit public, le Tribunal fédéral contrôle librement le respect du droit fédéral, qui comprend les droits de nature constitutionnelle (cf. art. 95 let. a et 106 al. 1 LTF), sous réserve des exigences de motivation figurant à l'<ref-law>. Aux termes de cet alinéa, le Tribunal fédéral n'examine la violation de droits fondamentaux que si ce grief a été invoqué et motivé par le recourant, à savoir exposé de manière claire et détaillée (<ref-ruling> consid. 1.7.2 p. 106; <ref-ruling> consid. 1.3 p. 41).
2.2. Le Tribunal fédéral conduit son raisonnement juridique sur la base des faits constatés par l'autorité précédente (<ref-law>), sous réserve des cas prévus à l'<ref-law>. Selon l'<ref-law>, le recours ne peut critiquer les constatations de fait que si les faits ont été établis de façon manifestement inexacte - notion qui correspond à celle d'arbitraire - ou en violation du droit au sens de l'<ref-law> et si la correction du vice est susceptible d'influer sur le sort de la cause (<ref-ruling> consid. 6 p. 358), ce que le recourant doit expliquer de manière circonstanciée (cf. <ref-law>). A défaut, il n'est pas possible de tenir compte d'un état de fait qui diverge de celui qui est contenu dans l'acte attaqué (arrêt 2C_70/2019 du 16 septembre 2019 consid. 2.2, destiné à la publication). Par ailleurs, aucun fait nouveau ni preuve nouvelle ne peut en principe être présenté devant le Tribunal fédéral (cf. <ref-law>). Les nova ne sont ainsi pas admissibles, qu'il s'agisse de faits ou moyens de preuve survenus postérieurement à la décision attaquée, ou d'éléments que les parties ont négligé de présenter aux autorités cantonales (cf. <ref-ruling> consid. 3.1.2 p. 123).
2.3. Dans la mesure où le recourant 1 présente une argumentation partiellement appellatoire, en complétant librement l'état de fait retenu dans l'arrêt entrepris, sans invoquer l'arbitraire en lien avec l'établissement des faits ou l'appréciation des preuves, ni démontrer en quoi les faits retenus par l'instance précédente auraient été établis de manière insoutenable ou en violation du droit, le Tribunal fédéral ne peut pas en tenir compte. La Cour de céans statuera donc sur la base des faits tels qu'ils ressortent de l'arrêt attaqué.
Par ailleurs, s'agissant des pièces que l'intéressé a produites à l'appui de son recours, à savoir neuf attestations de bénévolat et de formation le concernant, dont deux établies postérieurement à l'arrêt entrepris, ainsi que trois documents concernant le salaire, respectivement les prestations d'assurance-invalidité de sa fiancée, celles-ci ne seront pas prises en considération, dans la mesure où elles sont nouvelles au sens de l'<ref-law>, respectivement où l'on ne voit pas ce qui aurait empêché l'intéressé de les produire devant l'autorité précédente. Quant à l'attestation médicale du 14 décembre 2018 établie par le Dr. C._, celle-ci figure déjà au dossier.
3.
Le litige porte sur le droit du recourant 1 d'obtenir une autorisation de séjour en Suisse en vue de mariage. A ce sujet, l'intéressé ne fait valoir, à juste titre, aucun droit découlant de la loi fédérale du 16 décembre 2005 sur les étrangers (LEtr, intitulée, depuis le 1er janvier 2019, loi fédérale sur les étrangers et l'intégration [LEI; RO 2017 6521]). En effet, en l'absence de projet concret de mariage (cf. infra consid. 4.2), les autorités ne sauraient être contraintes de lui accorder une autorisation de courte durée au sens de l'art. 17 al. 2 LEI dans ce but (cf. <ref-ruling> consid. 3.5.2 p. 48; <ref-ruling> ss). Il soutient uniquement que le refus de lui accorder l'autorisation de séjour sollicitée est contraire à l'art. 8 CEDH, compte tenu de la durée et de la stabilité de la relation nouée avec sa concubine de nationalité suisse.
4.
4.1. Un étranger peut, selon les circonstances, se prévaloir de l'art. 8 par. 1 CEDH, qui garantit le droit au respect de la vie privée et familiale, pour s'opposer à l'éventuelle séparation de sa famille, pour autant qu'il entretienne une relation étroite et effective avec une personne de sa famille ayant le droit de résider durablement en Suisse (<ref-ruling> consid. 2.1 p. 336 et les références citées). D'après une jurisprudence constante, les relations visées par l'art. 8 CEDH sont avant tout celles qui concernent la famille dite nucléaire, soit celles qui existent entre époux ainsi qu'entre parents et enfants mineurs vivant en ménage commun (cf. <ref-ruling> consid. 6.1 p. 12). Sous réserve de circonstances particulières, les concubins ne sont donc pas habilités à invoquer l'art. 8 CEDH.
Sous cet angle, le Tribunal fédéral a précisé à de nombreuses reprises que l'étranger qui vit en union libre avec un ressortissant suisse ou une personne ayant le droit de s'établir en Suisse ne peut prétendre à une autorisation de séjour que s'il entretient depuis longtemps des relations étroites et effectivement vécues avec son concubin ou s'il existe des indices concrets d'un mariage sérieusement voulu et imminent (arrêt 2C_401/2018 du 17 septembre 2018 consid. 6 et les arrêts cités; arrêt 2C_481/2017 du 15 décembre 2017 consid. 4.2 et les arrêts cités). En particulier, la jurisprudence a souligné qu'une durée de vie commune de trois ans, respectivement de quatre ans, sans la présence d'enfant et de projet de mariage imminent, était insuffisante pour qu'un couple de concubins puisse se prévaloir d'une relation atteignant le degré de stabilité et d'intensité requis pour pouvoir être assimilée à une union conjugale protégée par l'art. 8 CEDH (cf. arrêts 2C_832/2018 du 29 août 2019 consid. 2.2 et 2C_97/2010 du 4 novembre 2010 consid. 3.3, respectivement arrêt 2C_1035/2012 du 21 décembre 2012 consid. 5.2). Par ailleurs, la jurisprudence de la Cour européenne des droits de l'homme n'a accordé une protection à des couples de concubins, sous l'angle de l'art. 8 CEDH, qu'à des relations qui étaient bien établies dans la durée, soit de six à vingt-six ans, et pour des couples qui, en outre, vivaient avec des enfants (arrêts Serife Yigit c. Turquie du 2 novembre 2010, no 3976/05, § 94 et 96 et les références; Emonet et autres c. Suisse du 13 décembre 2007, no 39051/03, § 34 et 36). Enfin, si dans une affaire Keegan c. Irlande du 26 mai 1994, no 16969/90, ladite Cour a admis qu'une union libre qui n'avait duré que deux ans tombait sous l'empire de la protection de la vie familiale, c'était parce que les concubins avaient, d'une part, conçu un enfant ensemble et, d'autre part, formé le projet de se marier.
4.2. En l'occurrence, il ressort de l'arrêt entrepris, d'une manière qui lie le Tribunal fédéral (<ref-law>, cf. supra consid. 2.3), que l'intéressé vit une relation stable avec sa concubine, de nationalité suisse, depuis 2015, soit depuis plus de quatre ans. Cette vie commune a par ailleurs, selon une attestation médicale du 14 décembre 2018, un effet favorable sur le plan de la santé psychique de l'intéressée. Le couple n'a toutefois pas d'enfant et ne vit pas avec des enfants. Par ailleurs, le recourant 1 reconnaît lui-même - à juste titre - que la condition du mariage imminent fait défaut, dans la mesure où il n'a pas été en mesure de fournir, sur une période de plus de deux ans, les documents propres à établir de manière fiable ses données personnelles et sa capacité matrimoniale. Un tel constat est d'autant plus vrai qu'aucune procédure préparatoire de mariage n'est, selon les faits de l'arrêt entrepris, actuellement ouverte ou pendante.
4.3. Dans ces conditions, force est de constater que les circonstances du cas d'espèce ne permettent pas d'assimiler la relation entre les intéressés à une véritable union conjugale, compte tenu de la jurisprudence précitée (cf. supra consid. 4.1). Le recourant 1 ne peut par conséquent en tirer de manière défendable un droit conféré par l'art. 8 CEDH lui permettant de rester en Suisse.
4.4. Par surabondance, l'arrêt entrepris ne relève aucun élément déterminant qui ferait apparaître le refus de l'autorisation de séjour en vue de mariage comme disproportionné (cf. art. 96 LEI). En particulier, il ressort des constatations cantonales que l'intéressé est âgé de 39 ans, est en bonne santé et a passé les 34 premières années de sa vie au Cameroun, où il a donc vraisemblablement tissé non seulement des attaches familiales, mais encore sociales et culturelles importantes. Sa réintégration dans son pays d'origine, même si elle supposera une période de réadaptation, n'apparaît ainsi nullement compromise. Son éloignement ne l'empêchera par ailleurs pas de maintenir des contacts avec sa fiancée, par le biais des moyens modernes de communication ou de séjours touristiques. Au demeurant, cette dernière ne pouvait ignorer, comme le relève à juste titre l'autorité précédente, qu'elle risquait de devoir vivre sa relation de manière séparée, dans la mesure où, lorsqu'ils se sont rencontrés, l'intéressé séjournait illégalement en Suisse et que son statut demeurait très précaire. On relèvera enfin que, bien qu'il ne puisse être exigé de sa fiancée qu'elle aille vivre au Cameroun, rien n'empêche cette dernière de s'y rendre afin d'y épouser le recourant, avant de requérir, une fois revenue en Suisse, le regroupement familial en faveur de son conjoint, conformément à l'art. 42 LEI.
5.
Les considérants qui précèdent conduisent au rejet du recours dans la mesure de sa recevabilité. Celui-ci étant d'emblée dénué de chance de succès, la requête d'assistance judiciaire est rejetée (<ref-law>). Les frais, calculés en tenant compte de la situation précaire des recourants 1 et 2, seront mis à la charge de ceux-ci, qui succombent, solidairement entre eux (art. 66 al. 1 et 5 LTF). Il n'est pas alloué de dépens (art. 68 al. 1 et 3 LTF).

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 des recourants, solidairement entre eux.
4.
Le présent arrêt est communiqué au représentant des recourants, au Service de la population du canton de Vaud, au Tribunal cantonal du canton de Vaud, Cour de droit administratif et public, et au Secrétariat d'Etat aux migrations.
Lausanne, le 24 février 2020
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président : Seiler
Le Greffier : Rastorfer