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.