Faits : A. A.a. A.X._, ressortissant togolais né en 1980, est entré en Suisse le 26 février 2007, avec son épouse coutumière, l'enfant commun du couple, ainsi que son neveu B.X._, né en 2001. Le même jour, la famille a déposé une demande d'asile, qui a été rejetée par l'Office fédéral des migrations (devenu entretemps le Secrétariat d'Etat aux migrations; ci-après: le SEM) le 14 août 2008. Cette décision a été confirmée sur recours par le Tribunal administratif fédéral le 2 octobre 2012. A.X._ et son épouse coutumière se sont séparés en janvier 2010. Le 21 juin 2010, le couple a eu une fille. Les deux enfants communs du couple sont restés vivre auprès de la mère, alors que B.X._ a suivi son oncle. A.b. Le 22 septembre 2010, A.X._ et sa fiancée, une ressortissante française résidant en Suisse, ont déposé une demande en vue du mariage auprès des autorités fribourgeoises. Le 3 octobre 2011, le couple a eu un enfant, C.X._, ressortissant français (art. 105 al. 2 LTF). A la suite du mariage, qui a eu lieu le 5 octobre 2012, A.X._ a obtenu une autorisation de séjour UE/AELE valable jusqu'au 1er janvier 2015. Son neveu B.X._, dont il a la garde, a été mis au bénéfice de la même autorisation. Les conjoints ont pris un domicile séparé à partir du 1er octobre 2013. Lors d'une audition administrative qui s'est déroulée le 1er avril 2014, l'épouse a déclaré entretenir une nouvelle relation et ne pas envisager de reprendre la vie commune. Par jugement du 24 juin 2014, le Tribunal d'arrondissement de la Sarine a prononcé la séparation judiciaire des époux. La garde sur C.X._ a été attribuée à sa mère, son père bénéficiant, à défaut d'entente, d'un droit de visite à raison d'un week-end sur deux. Par décision du 27 janvier 2015, la Justice de Paix de l'arrondissement de la Sarine a institué une curatelle de surveillance des relations personnelles au sens de l'art. 308 al. 2 CC en faveur de C.X._, compte tenu des difficultés de communication et d'organisation relatives à l'exercice du droit de visite de son père. L'autorité a souligné dans sa décision que l'enfant parlait quotidiennement de son père, avec lequel il était important qu'il puisse partager des moments réguliers, mais que l'instabilité de la situation du père concernant le droit de visite compromettait le développement de l'enfant. A.X._ exerce son droit de visite sur son fils C.X._, mais il n'a jamais versé de contribution d'entretien en sa faveur. A.c. Sur le plan professionnel, l'intéressé travaille à 40% au sein de D._, en qualité de responsable de la coordination des activités et de la permanence de l'association, pour un salaire mensuel brut de 1'850 fr. En outre, entre novembre 2014 et mai 2015, il a travaillé à 30% comme enseignant auprès de la même association, pour un salaire horaire de 20 fr. Parallèlement à ces activités, A.X._ est engagé comme catéchiste et président du mouvement E._ de la paroisse Y._ à Fribourg, président et fondateur de l'association F._, ainsi que délégué du Conseil de G._. Il a également été entraîneur de football pour une équipe fribourgeoise de jeunes. Sur le plan financier, A.X._ faisait l'objet, au 11 avril 2014, de poursuites pour 161 fr. 45 et d'actes de défaut de biens s'élevant à 12'747 fr. 15. Il a en outre été assisté par le Service de l'aide sociale de la Ville de Fribourg jusqu'en janvier 2014, pour un montant total de 3'892 fr. 85. Aucune démarche de remboursement de ce montant n'est en cours. A.d. Durant son séjour en Suisse, A.X._ a fait l'objet de deux condamnations pénales. Le 4 juin 2013, il a été condamné à une amende de 200 fr. pour avoir refusé de décliner son identité. Le 3 février 2014, il a été condamné à une peine pécuniaire de 10 jours-amende à 30 fr., avec sursis, pour violation de l'obligation d'entretien envers sa fille. A.e. B.X._ effectue sa scolarité obligatoire à Fribourg. Il joue au football dans une équipe fribourgeoise. Par ordonnance pénale du Juge des mineurs du 30 avril 2014, B.X._ a été reconnu coupable de contravention à la loi fédérale du 20 mars 2009 sur le transport de voyageurs (LTV; RS 745.1) et sanctionné d'une réprimande. Le 17 juin 2014, il a fait l'objet d'un rapport de dénonciation de la police de sûreté pour lésions corporelles simples, dommages à la propriété, injure, menaces, violation de domicile et violation du domaine secret ou du domaine privé au moyen d'un appareil de prise de vue. Cette dénonciation a donné lieu à une médiation, qui a abouti à un accord signé le 14 avril 2015. La procédure pénale a donc été classée le 1er mai 2015. Par ordonnance pénale du Juge des mineurs du 24 mars 2015, B.X._ a été reconnu coupable d'une contravention à la LTV et condamné à une amende de 60 fr. Enfin, l'intéressé fait actuellement l'objet d'une procédure pénale concernant le vol d'un cyclomoteur ainsi que des infractions à la loi fédérale du 19 décembre 1958 sur la circulation routière (LCR; RS 741.01). B. Le 8 janvier 2015, le Service de la population et des migrants du canton de Fribourg (ci-après: le Service cantonal) a refusé de renouveler les autorisations de séjour de A.X._ et B.X._ et a prononcé leur renvoi de Suisse dans un délai de 30 jours. Par arrêt du 18 décembre 2015, le Tribunal cantonal du canton de Fribourg (ci-après: le Tribunal cantonal) a rejeté le recours formé par A.X._ et B.X._ contre cette décision. C. A l'encontre de l'arrêt du 18 décembre 2015, A.X._ (le recourant 1) et B.X._ (le recourant 2) déposent un recours en matière de droit public auprès du Tribunal fédéral. Ils concluent, sous suite de dépens, à l'annulation de l'arrêt entrepris et à la prolongation de leurs autorisations de séjour. Il sollicitent en outre le bénéfice de l'assistance judiciaire. Le Tribunal cantonal renvoie aux considérants de son arrêt et conclut au rejet du recours. Le Secrétariat d'Etat aux migrations propose le rejet du recours. Le Service cantonal n'a pas formulé d'observations. Par ordonnance du 22 février 2016, le Président de la IIe Cour de droit public du Tribunal fédéral a accordé l'effet suspensif au recours. Le 22 juin 2016, A.X._ et B.X._ ont déposé des observations supplémentaires. Ils ont également produit des nouvelles pièces.