Faits :
A.
Ressortissant algérien né en 1961 en Algérie, A._ est entré en Suisse en 2008, où il a épousé une ressortissante suisse. A la suite de son mariage, il a été mis au bénéfice d'une autorisation de séjour au titre du regroupement familial, puis d'une autorisation d'établissement, avant d'obtenir en 2015 la nationalité suisse par naturalisation facilitée. Après le divorce des époux en 2016, le Secrétariat d'État aux migrations a annulé la naturalisation facilitée de A._ par décision du 23 mai 2017, que l'intéressé a contestée en vain auprès du Tribunal administratif fédéral (arrêt du 4 septembre 2018). Par arrêt du 12 octobre 2018 (cause 1C_535/2018), le Tribunal fédéral a déclaré irrecevable le recours que A._ a formé contre cet arrêt.
B.
Par décision du 17 février 2020, le Service des migrations de l'Office de la population du canton de Berne (ci-après: le Service cantonal) a révoqué l'autorisation d'établissement de A._, refusé de lui délivrer une autorisation de séjour et ordonné son renvoi de Suisse, en lui impartissant un délai au 30 mai 2020 pour quitter le pays. Par arrêt du 22 janvier 2021, le Tribunal administratif du canton de Berne (ci-après: le Tribunal cantonal) a rejeté son recours et lui a fixé un nouveau délai de départ au 11 mars 2021.
C.
Contre cet arrêt, A._ recourt au Tribunal fédéral. Il demande implicitement à pouvoir rester en Suisse, tout en requérant l'octroi d'un délai de départ plus long.
Il n'a pas été ordonné d'échange d'écritures.
Considérant en droit :
1.
Le Tribunal fédéral examine d'office et librement la recevabilité des recours qui lui sont soumis (art. 29 al. 1 LTF; cf. ATF 138 I 475 consid. 1 p. 476).
1.1. Le recourant n'a pas indiqué par quelle voie de droit il recourait devant le Tribunal fédéral, ce qui ne lui nuit pas, si son recours remplit les exigences légales de la voie de droit qui est ouverte en l'espèce (cf. ATF 138 I 367 consid. 1.1).
1.2. D'après l'art. 83 let. c ch. 2 LTF, le recours en matière de droit public est irrecevable contre les décisions en matière de droit des étrangers qui concernent une autorisation à laquelle ni le droit fédéral ni le droit international ne donnent droit. En l'occurrence, le recourant a perdu la nationalité suisse obtenue par la voie de la naturalisation facilitée par une décision définitive et exécutoire (art. 61 LTF), de sorte qu'il est redevenu un étranger au sens de la loi fédérale du 16 décembre 2005 sur les étrangers et l'intégration (LEI; RS 142.20). Le recourant se retrouve dès lors, au plan du droit des étrangers, dans la situation qui était la sienne avant ladite naturalisation, à savoir au bénéfice d'une autorisation d'établissement, sous réserve de motifs qui entraînent la perte de son statut (cf. ATF 135 II 1 consid. 3.2, 3.7 et 3.8). En l'occurrence, le Tribunal cantonal a jugé que le recourant ne pouvait pas bénéficier à nouveau de l'autorisation d'établissement qui était la sienne avant qu'il ne soit naturalisé, en raison de l'existence de motifs de révocation. La voie du recours en matière de droit public est ouverte contre une telle décision, puisqu'il existe en principe un droit au maintien de l'autorisation d'établissement (ATF 135 II 1 consid. 1.2.1), étant rappelé que le point de savoir si tel est le cas en l'espèce relève du fond et non de la recevabilité (cf. ATF 136 II 177 consid. 1.1).
Le recours a par ailleurs été formé en temps utile (art. 100 al. 1 LTF) contre une décision finale (art. 90 LTF) rendue par une autorité cantonale supérieure de dernière instance (art. 86 al. 1 let. d et al. 2 LTF) par le recourant, qui a qualité pour agir (cf. art. 89 al. 1 LTF). Il convient donc d'entrer en matière sur le recours en tant que recours en matière de droit public.
1.3. Le recourant demande notamment l'octroi d'un délai plus long pour quitter le pays.
La fixation par le Tribunal cantonal d'un délai de départ pour quitter la Suisse est liée au renvoi du recourant (cf. art. 64d al. 1 LEI). En matière de renvoi, le recours en matière de droit public n'est pas ouvert; seule la voie du recours constitutionnel subsidiaire est possible (art. 83 lit. c ch. 4 LTF en lien avec l'art. 113 LTF; arrêt 2D_36/2017 du 24 octobre 2017 consid. 1). Dans le cadre de ce recours toutefois, seule la violation de droits constitutionnels peut être invoquée (cf. art. 116 LTF) et doit faire l'objet d'une motivation claire (art. 106 al. 2 LTF par renvoi de l'art. 117 LTF). En l'occurrence, le recourant n'invoque aucun grief de cet ordre dans son mémoire. Son recours est partant irrecevable sur ce point.
1.4. Un mémoire doit notamment indiquer les motifs et ceux-ci doivent exposer succinctement en quoi l'acte attaqué viole le droit (cf. art. 42 al. 1 et 2 LTF), sous peine d'irrecevabilité dans les cas d'insuffisance manifeste (art. 108 al. 1 let. b LTF). En l'occurrence, il n'est pas évident de déceler en quoi le recourant reproche au Tribunal cantonal d'avoir violé le droit dans l'arrêt attaqué. Le recourant ne prend par ailleurs pas de conclusions formelles, comme le prescrit l'art. 42 al. 1 LTF. La recevabilité de son recours est partant très douteuse. Dès lors que le recours doit être rejeté, cette question souffre de rester indécise.
1.5. Il convient donc d'entrer en matière sur le recours en tant que recours en matière de droit public, sous réserve de ce qui suit. En raison de l'effet dévolutif du recours au Tribunal cantonal (cf. ATF 136 II 101 consid. 1.2), seul l'arrêt de cette instance fait l'objet de la présente procédure. Il n'y a donc pas lieu de s'attarder sur le grief que le recourant formule à l'encontre du Service cantonal, qu'il semble soupçonner d'avoir volontairement attendu, pour révoquer son autorisation d'établissement, l'entrée en vigueur, le 1er janvier 2019, de la révision de la loi fédérale sur les étrangers, si ce n'est pour souligner que, lorsque l'arrêt du Tribunal fédéral du 12 octobre 2018, qui a entraîné l'entrée en force de l'annulation de la naturalisation facilitée du recourant et le réexamen subséquent, par le Service cantonal, de son droit au séjour, a été rendu, les dispositions topiques qui entrent en ligne de compte en l'espèce (cf. infra consid. 4. et 5) existaient déjà et n'ont pas été modifiées au 1 er janvier 2019.
2.
Saisi d'un recours, le Tribunal fédéral applique le droit d'office (art. 106 al. 1 LTF), sous réserve des situations visées à l'art. 106 al. 2 LTF.
3.
3.1. Pour statuer, le Tribunal fédéral se fonde sur les faits constatés par l'autorité précédente (cf. art. 105 al. 1 LTF). Le recourant ne peut critiquer les constatations de fait que si celles-ci ont été effectuées en violation du droit au sens de l'art. 95 LTF ou de manière manifestement inexacte, c'est-à-dire arbitraire, et si la correction du vice est susceptible d'influer sur le sort de la cause (art. 97 al. 1 LTF; ATF 142 II 355 consid. 6). Les faits invoqués de manière appellatoire sont irrecevables (ATF 145 I 26 consid. 1.3; 144 II 281 consid. 3.6.2).
3.2. En l'espèce, le recourant ne se plaint pas d'un établissement inexact des faits, mais se prévaut d'éléments de fait qui, selon lui, font obstacle à un départ dans le délai qui lui a été imparti par le Tribunal cantonal. Outre que ces faits, non constatés dans l'arrêt attaqué, sont présentés de manière appellatoire, ils sont liés à une question qui ne peut faire l'objet d'un recours en matière de droit public, qui est la seule voie ouverte en l'espèce (cf. supra consid. 1.2 et 1.3). Par ailleurs, les faits que le recourant mentionne au sujet de son mariage et de son divorce le sont de manière également appellatoire et n'ont pas de lien avec l'objet du litige (cf. infra consid. 4). Le Tribunal fédéral n'en tiendra donc pas compte et statuera exclusivement sur la base des faits constatés dans l'arrêt attaqué.
4.
Le litige porte seulement sur le point de savoir si c'est à bon droit que le Tribunal cantonal a jugé que le recourant ne pouvait pas poursuivre son séjour en Suisse ensuite de l'annulation de sa naturalisation facilitée. La question de l'annulation de la naturalisation facilitée du recourant a en effet été réglée dans une autre procédure, et la décision qui a été rendue à cet égard est définitive et exécutoire depuis l'arrêt du 12 octobre 2018 du Tribunal fédéral (cf. supra consid. A; art. 61 LTF). C'est partant en vain que le recourant y revient dans son recours.
4.1. Selon la jurisprudence, l'étranger dont la naturalisation facilitée a été annulée ne doit pas se trouver dans une situation moins favorable que celle dont il bénéficiait avant sa naturalisation et qu'il aurait conservée s'il n'avait pas été naturalisé; il retrouve ainsi, du point de vue du droit des étrangers, le statut juridique antérieur qui était le sien avant la naturalisation, pour autant qu'aucun motif d'extinction ou de révocation dudit statut ne soit entre-temps apparu, point sur lequel il appartient à l'autorité du droit des étrangers de se prononcer, sur la base de la situation actuelle. Comme déjà indiqué (cf. supra consid. 1.2), si, avant l'annulation de la naturalisation facilitée, l'étranger était titulaire d'une autorisation d'établissement, il retrouve ce statut, sous réserve de motifs entraînant la perte de celui-ci (ATF 135 II 1 consid. 3.2, 3.7 et 3.8). Il faut donc, dans un tel cas, examiner s'il existe des circonstances propres à entraîner la perte de l'autorisation d'établissement, à savoir s'il existe un motif de révocation et, si oui, si la révocation est conforme au principe de la proportionnalité (ATF 135 II 1 consid. 4.1). En l'occurrence, les juges précédents ont estimé que le recourant remplissait des motifs de révocation de l'autorisation d'établissement, que cette révocation était proportionnée et que, dans ces circonstances, il était superflu d'examiner s'il pouvait se prévaloir d'un droit au séjour.
4.2. Le litige revient donc d'abord à se demander si c'est à bon droit que le Tribunal cantonal a retenu des circonstances justifiant la révocation de l'autorisation d'établissement que le recourant a acquise avant sa naturalisation.
4.3. S'agissant du droit applicable, il convient de rappeler que le 1er janvier 2019 est entrée en vigueur une révision de la loi fédérale du 16 décembre 2006 sur les étrangers, rebaptisée à cette occasion loi fédérale sur les étrangers et l'intégration (LEI; RO 2017 6521). Cette révision n'a pas modifié l'art. 63 al. 1 let. d de la loi, en vigueur depuis le 1er janvier 2018 (RO 2016 2561), qui prévoit notamment que l'autorisation d'établissement peut être révoquée si l'étranger s'est vu retirer la nationalité suisse suite à une décision ayant force de chose jugée. Dès lors que l'art. 63 al. 1 let. d LEI était déjà en vigueur au moment de l'annulation de la naturalisation facilitée du recourant, qui est intervenue le 12 octobre 2018, cette disposition s'applique en l'espèce, sans qu'il soit nécessaire de se demander si, dans le cas de l'annulation de naturalisation d'une personne qui disposait auparavant d'une autorisation d'établissement, il convient d'appliquer le droit en vigueur au moment de l'annulation de la naturalisation facilitée ou au moment de l'ouverture de la procédure de réexamen des conditions de séjour de l'étranger, soit en l'espèce le 14 février 2019 selon l'arrêt attaqué (sur cette question, cf. arrêt 2C_814/2020 du 18 mars 2021 consid. 4.2).
4.4. L'art. 63 LEI prévoit les situations dans lesquelles une autorisation d'établissement peut être révoquée. Tel est notamment le cas si l'étranger lui-même ou une personne dont il a la charge dépend durablement et dans une large mesure de l'aide sociale (art. 63 al. 1 let. c LEI), ou si l'étranger a tenté d'obtenir abusivement la nationalité suisse ou si cette dernière lui a été retirée suite à une décision ayant force de chose jugée dans le cadre d'une annulation de la naturalisation au sens de l'art. 36 de la loi du 20 juin 2014 sur la nationalité suisse (LN; RS 141.0) (art. 63 al. 1 let. d LEI). Dans l'arrêt attaqué, les juges cantonaux ont estimé que le recourant remplissait ces deux motifs de révocation.
4.4.1. Le recourant a fait l'objet d'une décision d'annulation de sa naturalisation facilitée entrée en force depuis l'arrêt 1C_535/2018 du 12 octobre 2018 du Tribunal fédéral. Dans ces circonstances, c'est à bon droit que le Tribunal cantonal a jugé que le recourant remplissait le motif de révocation de l'art 63 al. 1 let. d LEI, dont le texte est clair.
4.4.2. Dans ces circonstances, il n'est pas nécessaire de s'attarder sur le second motif de révocation que le Tribunal cantonal a retenu, à savoir la dépendance durable et dans une large mesure de l'aide sociale au sens de l'art. 63 al. 1 let. c LEI. On se limitera à relever que le Tribunal cantonal a correctement exposé la jurisprudence rendue en la matière (cf., entre autres, les arrêts 2C_519/2020 du 21 août 2020 consid. 3.3; 2C_653/2019 du 12 novembre 2019 consid. 7.1; 2C_385/2014 du 19 janvier 2015 consid. 4.3), qu'il a constaté, en substance, que le recourant était soutenu en permanence et de manière importante par l'aide sociale depuis août 2016, aucun élément ne laissant penser que sa situation pourrait s'améliorer à l'avenir, et qu'il en a déduit à bon droit que le recourant remplissait de ce fait les conditions de révocation de l'art. 63 al. 1 let. c LEI.
4.5. Reste à déterminer si la révocation de l'autorisation d'établissement du recourant est conforme au principe de la proportionnalité (art. 96 LEI; ATF 139 I 16 consid. 2.2.1).
4.5.1. De jurisprudence constante, cette question doit être tranchée au regard de toutes les circonstances du cas d'espèce. Dans ce cadre, il y a lieu de prendre en considération la gravité de l'éventuelle faute commise par l'étranger, son degré d'intégration, la durée de son séjour en Suisse et les conséquences d'un renvoi (cf. ATF 139 I 145 consid. 2.4), ainsi que la part de responsabilité qui lui est imputable s'agissant de son éventuelle dépendance à l'aide sociale (arrêt 2C_452/2020 du 14 octobre 2020 consid. 3.2 et les références). L'intérêt public à la révocation de titre de séjour d'étrangers dépendant de l'aide sociale consiste avant tout à éviter que ces personnes continuent d'être à la charge de la collectivité publique à l'avenir (arrêts 2C_1026/2018 du 25 février 2021 consid. 6.3 et les références; 2C_452/2020 du 14 octobre 2020 consid. 3.2 et les références). S'agissant de la durée du séjour, plus celle-ci est longue, plus les conditions pour mettre fin au séjour en Suisse doivent être appréciées restrictivement (cf. ATF 135 II 377 consid. 4.4 et 4.5). Toutefois, l'importance de la durée du séjour ne pèse qu'un faible poids dans la balance des intérêts lorsque l'étranger a séjourné en Suisse à la faveur de titres de séjour obtenus en trompant les autorités (cf. arrêts 2C_1004/2018 du 11 juin 2019; 2C_754/2018 du 28 janvier 2019 consid. 6.2).
4.5.2. En l'occurrence, il ressort des faits constatés que le recourant, après avoir perçu des indemnités de chômage du 1er décembre 2014 au 30 juin 2016, dépend entièrement de l'aide sociale depuis août 2016, sans qu'aucun élément ne laisse penser que sa situation pourrait s'améliorer à l'avenir. Il a par ailleurs obtenu la nationalité suisse sur la base de déclarations mensongères. Dans ces circonstances, il y a un intérêt public important à son éloignement.
Sous l'angle de l'intérêt privé, le recourant ne peut pas se prévaloir d'une bonne intégration dans notre pays. Professionnellement, il n'a été, selon les constatations cantonales, actif que du 1er janvier 2010 au 30 novembre 2014 comme aide-concierge, à un taux variant de 25% à 35%, à quoi se sont ajoutés, durant cette période, deux brefs mandats temporaires en tant que scénographe. Sous l'angle familial, il est divorcé et n'a pas de famille en Suisse, et il ne ressort pas de l'arrêt attaqué qu'il puisse se prévaloir d'une intégration sociale d'une intensité particulière. En outre, s'il séjourne dans notre pays depuis plus de douze ans, la durée de son séjour ne joue pas un rôle important dans la pesée des intérêts, dès lors qu'il vit en Suisse depuis 2015 en vertu d'une décision de naturalisation facilitée qui a été obtenue sur la base de déclarations mensongères. Son retour en Algérie ne posera par ailleurs pas de difficultés particulières, dès lors que, âgé de 59 ans, il a vécu les 47 premières années de sa vie en Algérie. Dans son mémoire, il demande du reste avant tout au Tribunal fédéral de pouvoir rester suffisamment longtemps en Suisse pour pouvoir organiser son départ, ce qui montre que, même à ses yeux, un retour dans son pays est envisageable. En réalité, l'intérêt privé du recourant à rester en Suisse apparaît avant tout motivé par des raisons économiques. Or, le simple fait que sa situation personnelle et économique soit potentiellement plus favorable en Suisse qu'en Algérie ne constitue pas un motif suffisant pour permettre à un étranger de prolonger son séjour. L'intérêt privé du recourant à rester en Suisse est donc très faible.
Dans ces circonstances, on ne peut que confirmer le résultat de la pesée des intérêts opérée par le Tribunal cantonal, selon lequel l'intérêt public à l'éloignement du recourant prime son intérêt privé à demeurer en Suisse.
4.6. La révocation de l'autorisation d'établissement du recourant étant conforme au principe de la proportionnalité, l'examen de l'octroi d'une autorisation de séjour s'avère superflu (cf. arrêt 2C_327/2015 du 22 avril 2016 consid. 5.7). On ne peut donc reprocher au Tribunal cantonal de s'être abstenu d'examiner si le recourant remplissait les conditions d'octroi d'une autorisation de séjour.
5.
Les considérants qui précèdent conduisent au rejet du recours dans la mesure de sa recevabilité. Il appartiendra à l'autorité cantonale compétente de fixer un nouveau délai de départ au recourant.
Succombant, le recourant doit supporter les frais de la procédure fédérale (art. 66 al. 1 LTF). Il n'est pas alloué de dépens (art. 68 al. 1 et 3 LTF).
Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est rejeté dans la mesure de sa recevabilité.
2.
Les frais judiciaires, arrêtés à 2'000 fr., sont mis à la charge du recourant.
3.
Le présent arrêt est communiqué au recourant, à la Direction de la sécurité du 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 14 avril 2021
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président : Seiler
La Greffière : Vuadens