Faits : A. A.a. A._, ressortissant camerounais né en 1978, est entré en Suisse le 27 août 2007, dans le but de contracter mariage avec B._, ressortissante française née en 1983 titulaire à l'époque d'une autorisation de séjour UE/AELE. A la suite du mariage, qui a eu lieu le 6 février 2009 à Prilly (VD), A._ a été mis au bénéfice d'une autorisation de séjour UE/AELE, laquelle a ensuite été prolongée jusqu'au 25 novembre 2014. Aucun enfant n'est issu de cette union. A.b. Le 31 janvier 2011, A._ a quitté le domicile conjugal. Le 12 juin 2012, le conseil de l'intéressé a communiqué au Service de la population du canton de Vaud (ci-après: le Service cantonal) que les époux avaient repris la vie commune le 22 mai 2012. A._ et B._ ont ensuite pris un domicile séparé à partir du 20 décembre 2013. A une date indéterminée, l'épouse a déposé auprès de l'autorité compétente une requête de mesures protectrices de l'union conjugale, qu'elle a retirée le 16 juillet 2015. A.c. Sur le plan professionnel, A._ a occupé plusieurs emplois à durée limitée, notamment auprès de sociétés de travail temporaire, en les alternant avec des périodes d'inactivité. L'intéressé n'a en particulier exercé aucune activité professionnelle entre les mois de décembre 2008 et juillet 2010, ainsi qu'entre les mois de novembre 2013 et juin 2014. Entre 2012 et 2015, A._ a bénéficié de l'aide sociale, sa dette sociale s'élevant à 54'875 fr. 10 le 12 juillet 2016. Le 25 avril 2016, il a déclaré au Service cantonal faire l'objet de poursuites pour un montant de 12'186 fr. et d'actes de défaut de biens s'élevant à 7'752 fr. 90. A.d. Depuis son arrivée en Suisse, A._ a été condamné pénalement à deux reprises. Le 11 juin 2012, il a été condamné à une peine pécuniaire de 150 jours-amende à 25 fr. avec sursis pour escroquerie. Le 6 juin 2014, il a été condamné à une peine pécuniaire de 30 jours-amende à 30 fr. pour détournement de valeurs patrimoniales mises sous main de justice, peine partiellement complémentaire à celle prononcée le 11 juin 2012. A.e. Pendant son séjour en Suisse, A._ s'est rendu régulièrement au Cameroun, pays dans lequel résident ses parents et une partie de ses frères et soeurs. B. Par décision du 8 décembre 2017, après avoir donné à A._ la possibilité d'exercer son droit d'être entendu, le Service cantonal a refusé de renouveler l'autorisation de séjour UE/AELE de l'intéressé, rejeté une requête de celui-ci tendant à l'octroi d'une autorisation d'établissement et prononcé son renvoi de Suisse. Par arrêt du 21 novembre 2018, le Tribunal cantonal du canton de Vaud (ci-après: le Tribunal cantonal) a rejeté le recours formé par A._ contre cette décision. Les juges cantonaux ont retenu, en substance, que l'intéressé vivait séparé de son épouse depuis environ cinq ans et que, dans ces conditions, il ne pouvait pas invoquer son mariage pour en déduire un droit de séjour en Suisse. L'autorité précédente a également considéré que A._ n'était pas intégré en Suisse, qu'aucune raison personnelle majeure ne s'opposait à son retour au Cameroun et que, au vu de l'ensemble des circonstances, l'intéressé ne pouvait rien tirer du droit à la protection de sa vie privée consacré par la CEDH. C. A l'encontre de l'arrêt du 21 novembre 2018, A._ dépose un recours en matière de droit public auprès du Tribunal fédéral. Il conclut, sous suite de frais et dépens, à l'annulation de l'arrêt entrepris et de la décision du Service cantonal du 8 décembre 2017, ainsi qu'au renouvellement de son autorisation de séjour. Subsidiairement, il demande le renvoi de la cause au Tribunal cantonal pour nouvelle décision dans le sens des considérants. Il sollicite également l'octroi de l'assistance judiciaire. Le Service cantonal et le Tribunal cantonal renoncent à se déterminer. Par ordonnance du 9 janvier 2019, le Président de la IIe Cour de droit public du Tribunal fédéral a accordé l'effet suspensif au recours.