Citation: 2C_976/2019 E. 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.