Faits :
A.
A._, né le 2 mars 1983, originaire du Yémen, est entré en Suisse en octobre 2000 et a déposé une requête d'asile. Le 19 décembre 2002, sa requête a été rejetée et son renvoi prononcé. A la suite d'une nouvelle demande, l'intéressé a obtenu le droit d'asile par décision du 13 novembre 2008, puis une autorisation d'établissement. Le 16 mars 2009, il s'est marié au Yémen avec une ressortissante de ce pays. Deux enfants, nés en 2010 et 2013, sont issus de cette union.
Le 15 décembre 2010, A._ a déposé une demande de naturalisation auprès de la Commune municipale d'Aegerten pour lui-même et son fils aîné. Le Conseil communal de la commune a rejeté cette demande par décision du 25 avril 2012. Le 22 octobre 2012, la Préfecture de Bienne a admis le recours interjeté par l'intéressé contre ladite décision en raison de son manque de motivation et a renvoyé la cause à la Commune. Le Conseil municipal a, le 5 novembre 2012, promis à l'intéressé l'octroi du droit de cité communal et remis le dossier à l'Office cantonal de la population et des migrations, qui a lui-même transmis la demande de naturalisation à l'Office fédéral des migrations (l'ODM, devenu le Secrétariat d'Etat aux migrations depuis le 1er janvier 2015, ci-après: le SEM) le 18 janvier 2013. Ce dernier a accordé l'autorisation de naturalisation le 28 mai 2014.
Le 11 décembre 2013, le nouvel art. 7 Cst./BE prévoyant notamment que l'octroi du droit de cité est refusé à quiconque bénéficie des prestations de l'aide sociale ou n'a pas entièrement remboursé les prestations perçues, est entré en vigueur.
Dès réception de l'autorisation fédérale de naturalisation, l'Office cantonal de la population et des migrations a instruit plus avant la demande de naturalisation de l'intéressé, notamment eu égard à l'entrée en vigueur du nouvel article 7 al. 3 let. b Cst./BE. Par décision du 18 janvier 2016, la Direction de la police et des affaires militaires du canton de Berne a rejeté la demande de naturalisation ordinaire de l'intéressé, au motif qu'il n'avait pas remboursé les prestations d'aide sociale perçues.
B.
Par arrêt du 2 août 2016, le Tribunal administratif du canton de Berne a rejeté le recours interjeté par A._ contre la décision du 18 janvier 2016.
C.
Agissant par la voie du recours constitutionnel subsidiaire, A._ demande principalement au Tribunal fédéral d'annuler l'arrêt du 2 août 2016, de constater la violation de ses droits constitutionnels dans la présente procédure et de lui accorder la nationalité suisse. Il conclut subsidiairement au renvoi de la cause à l'instance précédente pour nouvelle décision au sens des considérants. Il requiert aussi l'assistance judiciaire.
La Commune municipale d'Aegerten conclut au rejet du recours. Le Tribunal administratif a présenté des observations. Le recourant a répliqué, par courrier du 14 novembre 2016.

Considérant en droit :
1.
Le recours en matière de droit public (<ref-law>) est irrecevable contre les décisions relatives à la naturalisation ordinaire (<ref-law>). Le recours constitutionnel subsidiaire est par conséquent ouvert (<ref-law>).
1.1. A qualité pour former un tel recours celui qui a pris part à la procédure devant l'autorité précédente (<ref-law>) et a un intérêt juridique à l'annulation ou à la modification de la décision attaquée (<ref-law>). En l'espèce, le recourant, qui a pris part à la procédure devant l'instance précédente, peut se prévaloir d'un intérêt juridique protégé dans la mesure où il se prévaut notamment de l'interdiction de l'arbitraire (art. 9 Cst.; cf. <ref-ruling> consid. 1.4 p. 309 ss).
1.2. Le recours constitutionnel subsidiaire ne peut être formé que pour violation des droits constitutionnels (<ref-law>). En vertu de l'<ref-law>, applicable par renvoi de l'<ref-law>, les griefs y relatifs doivent être invoqués et motivés de façon détaillée en précisant en quoi consiste la violation, sous peine d'irrecevabilité (<ref-ruling> consid. 3 p. 237).
2.
A la citoyenneté suisse toute personne qui possède un droit de cité communal et le droit de cité du canton (art. 37 al. 1 Cst.). Les étrangères et étrangers obtiennent la nationalité suisse par la naturalisation dans un canton et une commune (après une procédure régie par le droit cantonal) sous réserve d'une autorisation fédérale accordée par l'office compétent (art. 12 al. 1 et 2 et 15a al. 1 de la loi fédérale du 29 septembre 1952 sur l'acquisition et la perte de la nationalité suisse [LN, RS 141.0]). Ces trois niveaux de la nationalité suisse sont indissolublement liés (Auer/Malinverni/Hottelier, Droit constitutionnel suisse, vol. I, 2013, n. 385 ss, 388).
Les conditions minimales d'aptitude à la naturalisation sont prévues par l'art. 14 de la loi fédérale sur la nationalité du 29 septembre 1952 (LN; RS 141.0; cf. également art. 38 al. 2 Cst.). Selon cette disposition, pour déterminer si un candidat est apte à la naturalisation, il convient en particulier d'examiner s'il s'est intégré dans la communauté suisse (let. a), s'il s'est accoutumé au mode de vie et aux usages suisses (let. b), s'il se conforme à l'ordre juridique suisse (let. c) et s'il ne compromet pas la sûreté intérieure ou extérieure de la Suisse (let. d).
2.1. Dans le canton de Berne, le droit de cité cantonal repose sur le droit de cité communal, lequel est garanti par le conseil communal sous réserve de l'octroi du droit de cité cantonal (art. 7 al. 2 Cst/BE; art. 2 al. 1 en relation avec art. 12 de la loi cantonale du 9 septembre 1996 sur le droit de cité cantonal et le droit de cité communal [LDC, RSB 121.1]; art. 14 al. 1 de l'ordonnance cantonale du 1 er mars 2006 sur la procédure de naturalisation et d'admission au droit de cité [ONat, RSB 121.111]).
Le 24 novembre 2013, les citoyens bernois ont accepté la modification de l'art. 7 Cst/BE lors de la votation populaire sur l'initiative "Pas de naturalisation de criminels et de bénéficiaires de l'aide sociale". Le nouvel art. 7 al. 3 Cst/BE prévoit de nouvelles conditions (négatives) relatives à l'octroi du droit de cité. Celui-ci est ainsi notamment refusé à quiconque a été condamné pour un crime par un jugement entré en force ou à quiconque a été condamné par un jugement entré en force à une peine privative de liberté de deux ans au moins pour une infraction (let. a), bénéficie des prestations de l'aide sociale ou n'a pas entièrement remboursé les prestations perçues (let. b), ne peut justifier de bonnes connaissances d'une langue officielle (let. c), ne peut justifier de bonnes connaissances des institutions suisses et cantonales et de leur histoire (let. d) et ne dispose pas d'une autorisation d'établissement (let. e). La modification constitutionnelle est entrée en vigueur le 11 décembre 2013 et a obtenu la garantie de l'Assemblée fédérale le 11 mars 2015 (FF 2015 p. 2811).
L'ancien art. 7 al. 1 Cst/BE, en vigueur jusqu'au 10 décembre 2013, disposait (simplement) que la législation réglait l'acquisition et la perte du droit de cité cantonal et du droit de cité communal dans les limites du droit fédéral.
2.2. En ce qui concerne les conditions matérielles, le droit cantonal bernois se réfère à la législation fédérale: selon l'art. 8 al. 1 LDC, les ressortissants et ressortissantes étrangers qui remplissent les conditions nécessaires à l'octroi de l'autorisation de naturalisation accordée par la Confédération peuvent solliciter le droit de cité d'une commune municipale. L'art. 13 al. 1 ONat répète les quatre critères d'aptitude de la législation fédérale (art. 14 LN) et précise que le service communal compétent doit notamment vérifier si ces conditions sont réalisées.
Il n'existe aucun droit proprement dit à l'admission au droit de cité (art. 16 al. 1 LDC). Si les critères d'aptitude sont réalisés, chacune des trois autorités compétentes décide, selon son autonomie, si le requérant peut être naturalisé (JAB 2012 p. 193 consid. 2.2 et les références citées), sous réserve du respect des droits et des principes fondamentaux (<ref-ruling> consid. 1.4.6 p. 313).
3.
Dans un premier grief, le recourant reproche à l'instance précédente de ne pas avoir étudié son aptitude à la naturalisation au sens de l'art. 14 LN. Il n'explique cependant pas en quoi un droit constitutionnel serait violé. La simple référence à l'art. 38 Cst. ne suffit pas, s'agissant d'une norme programmatique qui ne garantit pas un droit constitutionnel. Faute de respecter les exigences de motivation de l'<ref-law>, le grief doit être déclaré irrecevable.
4.
Ensuite, le recourant, qui ne nie pas ne pas avoir remboursé les prestations financières perçues de l'aide sociale, fait valoir que l'application à sa situation de la nouvelle teneur de l'art. 7 al. 3 Cst/BE enfreint le principe de non-rétroactivité, dès lors que les autorités communales lui ont promis le droit de cité communal avant l'entrée en vigueur de cette nouvelle disposition. Il se plaint d'une violation des art. 5 et 35 Cst. et 57 LN.
4.1. L'interdiction de la rétroactivité (proprement dite) des lois, qui découle des art. 5 al. 1 et 9 Cst., fait obstacle à l'application d'une norme à des faits entièrement révolus avant son entrée en vigueur (<ref-ruling> consid. 3.4 p. 193; cf., en droit privé, <ref-law>; <ref-ruling> consid. 2.1.1 p. 108). Il n'y a toutefois pas de rétroactivité proprement dite lorsque le législateur entend réglementer un état de choses qui, bien qu'ayant pris naissance dans le passé, se prolonge au moment de l'entrée en vigueur du nouveau droit. Cette rétroactivité improprement dite est en principe admise, sous réserve du respect des droits acquis (cf. <ref-ruling> consid. 6.3.2 p. 163; <ref-ruling> consid. 3.4 p. 193 s.; <ref-ruling> consid. 4.2 p. 374).
Selon la jurisprudence, la légalité d'un acte administratif doit être examinée en fonction de l'état de droit prévalant au moment de son prononcé, sous réserve de l'existence de dispositions transitoires; en conséquence, l'autorité de recours doit vérifier la bonne application du droit en vigueur au moment où l'autorité administrative a pris sa décision (<ref-ruling> consid. 11.1 p. 259 et les références citées).
4.2. En l'espèce, il n'est pas contesté qu'il n'y a pas de règle transitoire relative à l'application de l'art. 7 Cst/BE. Le recourant a déposé sa demande de naturalisation le 15 décembre 2010, soit avant l'entrée en vigueur du nouvel art. 7 Cst./BE. L'autorisation fédérale de naturalisation date du 28 mai 2014 et le refus de l'octroi du droit de cité cantonal du 18 janvier 2016.
La procédure de naturalisation est particulière en ce qu'elle exige trois décisions différentes de trois autorités différentes et indépendantes les unes des autres (promesse du droit de cité communal, autorisation de naturalisation de la Confédération, octroi du droit de cité cantonal). Quand bien même ces trois niveaux de la nationalité suisse sont indissolublement liés, le principe de l'état fédéral exige que l'autorité compétente en matière de naturalisation de chaque niveau de l'Etat (commune, canton et Confédération) statue conformément aux normes en vigueur pour elle au moment où elle rend sa décision et selon sa propre appréciation (Regina Kiener, in Biaggini/Gächter/ Kiener [éd.], Staatsrecht, 2 ème éd. 2015, § 29 n. 24; Céline Gutzwiller, Droit de la nationalité et fédéralisme en Suisse, 2008, p. 69 s., 496 s. et 499).
Dans le canton de Berne, l'art. 12 al. 2 LDC dispose que l'acquisition du droit de cité communal prend effet lorsque le droit de cité cantonal est accordé. L'art. 14 al. 1 ONat précise que le droit de cité communal est promis sous réserve de l'octroi du droit de cité cantonal. Le droit de cité cantonal est octroyé quant à lui sur la base de l'autorisation fédérale de naturalisation et sur la base de la promesse du droit de cité communal (art. 16 al. 2 ONat). Ces normes de coordination mettent en évidence le fait qu'il s'agit de trois procédures différentes qui se terminent chacune par une décision de l'autorité compétente et indépendante des deux autres. Ainsi, les voies de droit sont ouvertes contre chacune des trois décisions (art. 21 LDC et art. 51 LN).
Par conséquent, les autorités cantonales compétentes, appelées à statuer après l'octroi de l'autorisation fédérale du 28 mai 2014, devaient appliquer le droit en vigueur à ce moment-là. Elles n'ont pas violé le droit fédéral en appliquant les nouveaux critères de naturalisation de l'art. 7 al. 3 Cst/BE à la procédure litigieuse, et ce même si la promesse du droit de cité communal avait été accordée sur la base de l'ancien droit.
Par ailleurs, le recourant ne conteste pas ne pas avoir remboursé les prestations d'aide sociale perçues. C'est donc un cas de rétroactivité improprement dite dans la mesure où l'absence de remboursement de l'aide sociale perçue concerne un état de fait antérieur à l'entrée en vigueur de l'art. 7 Cst./BE mais qui perdure encore sous l'empire du nouveau droit. Il s'agit par conséquent d'un état de fait continu auquel le nouveau droit est applicable, qui ne conduit pas à la violation du principe de non-rétroactivité.
Mal fondé, le grief de la violation du principe de non-rétroactivité doit donc être écarté.
5.
Le recourant se plaint encore d'une violation du principe de la bonne foi, relevant un comportement contradictoire entre l'autorité communale qui a promis l'octroi du droit de cité et l'autorité cantonale qui plus tard le refuse en se fondant sur une nouvelle disposition constitutionnelle.
Aux termes de l'art. 5 al. 3 Cst., les organes de l'Etat et les particuliers doivent agir de manière conforme aux règles de la bonne foi. Cela implique notamment qu'ils s'abstiennent d'adopter un comportement contradictoire ou abusif. De l'art. 9 Cst. découle le droit de toute personne à la protection de sa bonne foi dans ses relations avec l'Etat (<ref-ruling> consid. 5.2 p. 261 et l'arrêt cité).
Fût-il suffisamment motivé au regard des exigences de l'<ref-law>, ce grief pourrait être d'emblée rejeté puisque le principe général de la protection de la bonne foi ne s'oppose en principe pas à un changement de loi (arrêt 1C_23/2014 du 24 mars 2015 consid. 7.4.4).
De plus, aucune promesse d'une autorité cantonale, qui aurait pu légitimement faire naître chez le recourant certaines attentes, n'a été donnée. En effet, la promesse de droit de cité communal ne constitue en aucun cas une promesse d'octroi du droit de cité cantonal, dès lors que la procédure communale est indépendante de la procédure cantonale (voir supra consid. 4.2).
6.
Le recourant affirme ensuite que le recours à l'aide sociale ne lui serait pas imputable. Il se prévaut d'une violation du droit au mariage et au respect de la vie privée (art. 13 Cst. et 8 CEDH). Il se contente cependant à cet égard d'affirmer que la cour cantonale "ne peut inférer sur le choix du partenaire ou de la répartition des tâches au sein du foyer de ses administrés". Il n'expose pas en quoi ces dispositions seraient violées. Faute de motivation satisfaisant aux exigences de l'<ref-law>, le grief est irrecevable.
7.
Le recourant se plaint encore d'une violation du principe de la proportionnalité (art. 36 al. 3 Cst.) et de l'interdiction d'arbitraire (art. 9 Cst.), dans la mesure où il se montre prêt à rembourser l'aide sociale perçue, si un laps de temps raisonnable lui est fixé pour le faire. Il met en avant les circonstances particulières, soit le fait qu'il a entamé la procédure sous l'ancien droit et que la procédure pour l'autorisation fédérale a duré longtemps.
A cet égard, l'instance précédente a retenu qu'il n'existait aucun droit à l'admission au droit de cité (art. 16 al. 1 LDC) - point qu'il y a cependant lieu de relativiser (cf supra consid. 2.2) - et que le séjour en Suisse du recourant et de sa famille n'était pas menacé; la situation actuelle du recourant ne lui permettait simplement pas d'acquérir la nationalité suisse. La cour cantonale a relevé qu'il apparaissait que le recourant ne séjournait en Suisse que depuis dix ans lorsqu'il avait déposé sa demande de naturalisation et qu'à la suite du rejet de sa demande d'asile en 2002 et du renvoi prononcé, il aurait dû quitter le pays en avril 2003; il n'avait, semble-t-il, pu rester en Suisse qu'en raison des recours ordinaires et extraordinaires qu'il avait déposés contre ce refus; ce n'était finalement que fin 2008 qu'il avait obtenu l'asile, à la suite d'une nouvelle demande formulée en mai 2007; enfin, ce n'était que depuis juillet 2014 qu'il ne percevait plus de prestations de l'aide sociale.
Sur la base de ces éléments, l'instance précédente pouvait confirmer sans violer le principe de proportionnalité le rejet de la demande du recourant, ce d'autant plus que l'obligation de restitution de prestations de l'aide sociale se prescrit au plus tard dix ans après le versement de chaque prestation (art. 45 al. 1 de la loi cantonale du 1 er janvier 2002 sur l'aide sociale [LASoc, RSB 860.1]; art. 3 al. 2 et 11 al. 2 let. h de l'ordonnance sur la procédure de naturalisation et d'admission au droit de cité du 1 er mars 2006 [ONat, RSB 121.111]) : le recourant pourrait ainsi, sans préjudice aucun du sort accordé à sa requête, déposer une nouvelle demande de naturalisation au plus tard mi-juillet 2024, ou antérieurement s'il a, dans l'intervalle, remboursé les prestations reçues.
8.
Le recourant relève enfin que cinq ans se sont écoulés entre le dépôt de sa requête de naturalisation et la décision cantonale de refus d'octroi du droit de cité cantonal. Il se plaint d'un déni de justice et d'une violation du principe de la célérité (art. 29 Cst. et 6 CEDH).
8.1. En vertu de l'art. 29 al. 1 Cst., toute personne a droit, dans une procédure judiciaire ou administrative, à ce que sa cause soit traitée équitablement et jugée dans un délai raisonnable.
Cette disposition consacre le principe de la célérité, ou, en d'autres termes, prohibe le retard injustifié à statuer. Viole la garantie ainsi accordée, l'autorité qui ne rend pas une décision qu'il lui incombe de prendre dans le délai prescrit par la loi ou dans le délai que la nature de l'affaire et les circonstances font apparaître comme raisonnable. Le caractère raisonnable du délai s'apprécie selon les circonstances particulières de la cause, eu égard en particulier à la complexité de l'affaire, au comportement du requérant et à celui des autorités compétentes, ainsi qu'à l'enjeu du litige pour l'intéressé (<ref-ruling> consid. 4.4). A cet égard, il appartient au justiciable d'entreprendre ce qui est en son pouvoir pour que l'autorité fasse diligence, que ce soit en l'invitant à accélérer la procédure ou en recourant, le cas échéant, pour retard injustifié. Si on ne peut lui reprocher quelques "temps morts", l'autorité ne saurait invoquer une organisation déficiente ou une surcharge structurelle pour justifier la lenteur de la procédure. Il appartient en effet à l'Etat d'organiser ses juridictions de manière à garantir aux citoyens une administration de la justice conforme aux règles (<ref-ruling> consid. 5.1 et 5.2 et les références).
8.2. En l'occurrence, il faut constater, à l'instar de l'instance précédente, qu'un temps relativement long s'est écoulé entre la demande de naturalisation et la décision cantonale de refus, soit un petit peu plus de cinq ans. Cette durée s'explique toutefois par la nature de la procédure de naturalisation, qui nécessite plus de temps qu'une autre procédure administrative, dès lors qu'elle implique des décisions de trois autorités étatiques différentes et indépendantes les unes des autres. La longueur de la procédure est en quelque sorte inhérente à la procédure ordinaire de naturalisation. S'ajoute à cela que dans la présente affaire la procédure a été émaillée d'un recours devant la Préfecture. Par ailleurs, si l'autorité fédérale a pris 16 mois pour rendre son autorisation, le recourant ne prétend pas l'avoir invitée à accélérer la procédure ou avoir recouru pour retard injustifié.
Dans ces conditions, on ne saurait admettre que le recourant est fondé à se plaindre d'un retard inadmissible à statuer; le grief doit être écarté.
9.
Il s'ensuit que le recours doit être rejeté, dans la mesure de sa recevabilité.
Dès lors que le recourant est dans le besoin et que ses conclusions ne paraissaient pas d'emblée vouées à l'échec, l'assistance judiciaire doit lui être accordée (<ref-law>). Le recourant requiert la désignation de Me Imed Abdelli en qualité d'avocat d'office. Il y a lieu de faire droit à cette requête et de fixer d'office les honoraires de l'avocat, qui seront supportés par la caisse du Tribunal fédéral (<ref-law>). Le recourant est en outre dispensé des frais judiciaires (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est rejeté, dans la mesure de sa recevabilité.
2.
Il n'est pas perçu de frais judiciaires.
3.
La demande d'assistance judiciaire est admise. Me Imed Abdelli est désigné comme défenseur d'office du recourant et ses honoraires, supportés par la caisse du Tribunal fédéral, sont fixés à 1'500 francs.
4.
Le présent arrêt est communiqué au mandataire du recourant, à la Commune municipale d'Aegerten, au Canton de Berne, au Tribunal administratif du canton de Berne, Cour des affaires de langue française, et au Secrétariat d'Etat aux migrations.
Lausanne, le 27 avril 2017
Au nom de la Ire Cour de droit public
du Tribunal fédéral suisse
Le Président : Merkli
La Greffière : Tornay Schaller