Faits :
A.
A.a. Ressortissant algérien né en 1973, A._ est entré en Suisse en 2006 et a été mis au bénéfice d'une autorisation de séjour dans le cadre d'un regroupement familial. Le 9 septembre 2009, le Service de la population et des migrants du canton de Fribourg (ci-après : le Service cantonal) a refusé le renouvellement de cette autorisation et prononcé le renvoi de Suisse de A._. Celui-ci a néanmoins bénéficié d'une autorisation de courte durée, valable jusqu'en avril 2012. N'ayant pas trouvé d'emploi, il a été sommé par le Service cantonal, le 24 avril 2012, de quitter la Suisse.
En juin 2012, l'Ambassade d'Algérie a fait savoir aux autorités suisses qu'elle était disposée à établir un laissez-passer en faveur de A._ (cf. <ref-law>).
A.b. Le 15 juillet 2015, A._ a été placé en détention administrative en vue de son renvoi pour une durée de trois mois. Le 14 octobre 2015, sur demande du Service cantonal, le Tribunal des mesures de contrainte du canton de Fribourg (ci-après : le Tribunal des mesures de contrainte) a transformé la détention en vue du renvoi en détention en phrase préparatoire et l'a prolongée jusqu'au 15 janvier 2016. Cette mesure a été confirmée le 6 novembre 2015 par la Ie Cour administrative du Tribunal cantonal du canton de Fribourg (ci-après : le Tribunal cantonal). La détention a cependant été levée le 1 er décembre 2015, avec effet au 24 novembre 2015, en vue de l'exécution d'une condamnation pénale à une peine privative de liberté. Par arrêt du 21 décembre 2015 (2C_1072/2015), le Tribunal fédéral a rejeté dans la mesure de sa recevabilité le recours qu'avait formé l'intéressé contre l'arrêt du Tribunal cantonal du 6 novembre 2015 (<ref-law>).
A.c. Le 13 août 2015, A._ a déposé une demande d'asile. Le 5 novembre 2015, le Secrétariat d'Etat aux migrations (ci-après : le Secrétariat d'Etat) a rejeté cette demande et prononcé le renvoi de Suisse de A._. Cette décision a été confirmée par le Tribunal administratif fédéral le 29 décembre 2015.
Le 25 juillet 2016, A._ a formé une nouvelle demande d'asile, sur laquelle le Secrétariat d'Etat n'est pas entré en matière, tout en ordonnant à l'intéressé de quitter la Suisse.
A.d. Sur le plan pénal, A._ a été condamné à 16 reprises entre le 10 août 2011 et le 30 avril 2018, pour vol, vol d'importance mineure, recel, dommages à la propriété, violation de domicile, violences ou menaces contre les autorités et les fonctionnaires, opposition aux actes de l'autorité, menaces, injures, diffamation, contrainte, utilisation abusive d'une installation de télécommunication, contravention à la loi fédérale du 20 mars 2009 sur le transport des voyageurs (LTV; RS 745.1) et à la LStup (RS 812.121), ainsi qu'infractions à la législation en matière d'étrangers. Une des condamnations sanctionne en outre des lésions corporelles graves (recte : tentative de lésions corporelles graves).
A.e. Le 4 mars 2019, le Service cantonal a placé A._ en détention en vue du renvoi pour une durée de trois mois. Cette mesure a été confirmée par le Tribunal des mesures de contrainte le 7 mars 2019, puis prolongée pour une durée de trois mois supplémentaires. Saisi d'un recours, le Tribunal cantonal a pris acte, le 25 juin 2019, de la décision du Service cantonal de libérer immédiatement l'intéressé de la détention en vue du renvoi (cf. <ref-law>). Deux vols à destination d'Alger réservés en juin 2019 avaient dû être annulés, car les autorités algériennes n'avaient pas délivré de laissez-passer à l'intéressé. Par arrêt du 2 juillet 2019 (2C_626/2019), le Tribunal fédéral a déclaré irrecevable le recours formé contre l'arrêt du 25 juin 2019 du Tribunal cantonal (cf. <ref-law>).
A.f. Le Secrétariat d'Etat a prononcé à l'encontre de A._ une interdiction d'entrée sur le territoire suisse le 17 mai 2019. Cette mesure fait l'objet d'un recours au Tribunal administratif fédéral.
A.g. Le 6 août 2019, A._ a formé une demande de reconsidération de la décision du Secrétariat d'Etat du 5 novembre 2015 rejetant sa demande d'asile. Le 11 septembre 2019, il a déposé une demande de visa auprès de l'Ambassade du Maroc, pays où vit sa mère. A cette même date, le Secrétariat d'Etat a refusé d'entrer en matière sur la demande de réexamen. Le Tribunal administratif fédéral a rejeté le recours formé contre cette décision le 26 septembre 2019.
Le 4 décembre 2019, A._ a demandé une nouvelle fois le réexamen de la décision du 5 novembre 2015. Par courrier du 13 décembre 2019, le Secrétariat d'Etat a indiqué à l'intéressé qu'il classait sans décision formelle cette demande, faute de nouveaux éléments (cf. art. 111b al. 4 de la loi fédérale sur l'asile du 26 juin 1998 [LASI; RS 142.3]) (cf. <ref-law>). Le 16 janvier 2020, le Tribunal administratif fédéral a retourné la demande du 4 décembre 2019, qui lui avait été transmise, au Secrétariat d'Etat comme objet de sa compétence.
A.h. En 2019, A._ a été condamné à trois reprises, pour vol, injure, diffamation, violence ou menace contre les autorités et les fonctionnaires, opposition aux actes de l'autorité, infractions à la législation en matière d'étrangers et infraction à la LCR (RS 741.01). La dernière condamnation, du 17 décembre 2019, consiste notamment en une peine privative de liberté d'un mois.
B.
Par décision du 30 décembre 2019, le Service cantonal a prononcé le placement de A._ en détention administrative pour insoumission, pour une durée d'un mois. Le 3 janvier 2020, après audition du détenu en présence de son conseil d'office, le Tribunal des mesures de contrainte a confirmé cette mesure. Le 10 janvier 2020, l'intéressé a formé un recours contre cette décision auprès du Tribunal cantonal.
Le 29 janvier 2020, la détention administrative pour insoumission a pris fin et A._ a été placé en détention pénale pour une durée de 30 jours.
Par arrêt du 14 février 2020, le Tribunal cantonal a rejeté le recours dans la mesure de sa recevabilité. En substance, il a retenu que le renvoi en Algérie était possible, que c'était le manque de coopération de l'intéressé qui empêchait la délivrance d'un laissez-passer par les autorités algériennes permettant de concrétiser ce renvoi et que la détention pour insoumission respectait le principe de proportionnalité.
C.
Contre l'arrêt du 14 février 2020, A._, agissant en personne, forme un "recours" au Tribunal fédéral. En substance, il se plaint d'être en détention depuis de nombreux mois et relève qu'il "ne peut pas et ne veut pas" retourner en Algérie. Il s'en prend également à la Présidente du Tribunal cantonal, à laquelle il reproche un manque d'impartialité. Il sollicite l'assistance judiciaire.
Par ordonnance présidentielle du 26 février 2020, la IIe Cour de droit public du Tribunal fédéral a renoncé à percevoir une avance de frais.
Le Tribunal cantonal renvoie aux considérants de son arrêt et conclut au rejet du recours. Le Service cantonal ne formule pas d'observations et se réfère à l'arrêt attaqué, ainsi qu'aux décisions précédentes. Le Secrétariat d'Etat a renoncé à déposer des observations.
Par décision du 27 février 2020, confirmée le même jour par le Tribunal des mesures de contrainte, le Service cantonal a placé A._ en détention administrative pour insoumission, à partir du 28 février 2020, date de la fin de l'exécution de sa peine privative de liberté, et ce pour une durée d'un mois (cf. <ref-law>).
Dans le délai de recours contre l'arrêt du 14 février 2020, le Tribunal fédéral a reçu deux courriers supplémentaires de A._. Dans le premier, il se plaint d'abus de pouvoir et sollicite l'octroi d'une autorisation de travail, ainsi que la "remise à zéro" de ses poursuites. Dans le second, il se dit victime de comportements pénalement répréhensibles de la part d'une des personnes travaillant pour le Service cantonal et demande que le Procureur fédéral soit saisi du dossier. Il critique par ailleurs la décision du 27 février 2020. Il cite aussi de nombreuses dispositions de la CEDH, des Protocoles no 7 et 12 à la CEDH, ainsi que de la législation en matière d'étrangers.

Considérant en droit :
1.
Le Tribunal fédéral examine d'office sa compétence (<ref-law>) et contrôle librement la recevabilité des recours qui lui sont soumis (<ref-ruling> consid. 2.1 p. 397).
1.1. Le recourant n'a pas qualifié son recours au Tribunal fédéral. Cette imprécision ne saurait lui nuire, pour autant que l'acte remplisse les exigences légales de la voie de droit qui est ouverte (cf. <ref-ruling> consid. 1.1 p. 370).
1.2. En matière de mesures de contrainte en droit des étrangers, le recours en matière de droit public est ouvert (<ref-law>; arrêt 2C_1038/2018 du 7 décembre 2018 consid. 1.1). En principe, la qualité pour déposer un recours en matière de droit public auprès du Tribunal fédéral (<ref-law>) suppose un intérêt actuel et pratique à obtenir l'annulation de la décision attaquée. Cet intérêt doit exister tant au moment du dépôt du recours qu'à celui où l'arrêt est rendu (<ref-ruling> consid. 1.3.1 p. 143). Le recours est déclaré irrecevable lorsque l'intérêt digne de protection fait défaut au moment du dépôt du recours. En revanche, si cet intérêt disparaît en cours de procédure, le recours devient sans objet (<ref-ruling> consid. 1.3.1 p. 143 et les arrêt cités). Le Tribunal fédéral fait toutefois exceptionnellement abstraction de l'exigence d'un intérêt actuel, lorsque la contestation peut se produire en tout temps dans des circonstances identiques ou analogues, que sa nature ne permet pas de la trancher avant qu'elle ne perde son actualité et que, en raison de sa portée de principe, il existe un intérêt public suffisamment important à la solution de la question litigieuse (<ref-ruling> consid. 1.3.1 p. 143; <ref-ruling> consid. 1.1 p. 208). La jurisprudence a par ailleurs admis que l'autorité de recours doit entrer en matière pour examiner la licéité de la détention administrative d'une personne libérée en cours de procédure, dans la mesure où le recourant invoque de manière défendable un grief fondé sur la CEDH (cf. <ref-ruling> consid. 1.3.1 p. 143 et les arrêts cités).
1.3. En l'espèce, l'arrêt attaqué du 14 février 2020 a confirmé la détention pour insoumission du recourant du 30 décembre 2019 au 29 janvier 2020. Le recourant a ensuite exécuté une condamnation pénale, puis il a été à nouveau placé, le 27 février 2020, en détention pour insoumission pour une durée d'un mois.
Au moment de son recours au Tribunal fédéral, le recourant n'avait donc, a priori, plus d'intérêt actuel à s'en prendre à l'arrêt du 14 février 2020. Toutefois, il se justifie en l'espèce de renoncer à l'exigence d'un intérêt actuel. En effet, le recourant a déjà été détenu une seconde fois pour insoumission et, comme la première fois, à l'issue de l'exécution d'une sanction pénale, ce qui démontre que le litige se reproduit dans des circonstances analogues. Compte tenu de la durée de la détention, il est en outre difficile, voire impossible que le Tribunal fédéral se prononce avant son échéance. Enfin, il existe un intérêt public suffisamment important à ce que la question de la détention pour insoumission du recourant soit tranchée, dès lors qu'est en cause le comportement des autorités algériennes et que le cas peut donc concerner plusieurs ressortissants algériens. Les conditions pour renoncer à l'exigence d'un intérêt actuel sont donc réunies. En revanche, les griefs tirés de la violation de la CEDH ne sont pas articulés de manière défendable, le recourant se contentant de citer diverses dispositions (cf. aussi infra consid. 3.2). Il sera donc entré en matière en l'espèce au titre de l'exception à l'exigence de l'intérêt actuel et non parce que le recourant fait valoir la violation de dispositions de la CEDH.
1.4. Au surplus, le recours est dirigé contre une décision finale (<ref-law>) émanant d'une autorité judiciaire cantonale de dernière instance (art. 86 al. 1 let. d et al. 2 LTF). Le recours et les courriers complémentaires reçus le 4 mars 2020 ont en outre été déposés en temps utile (<ref-law>). Dans la mesure où l'on comprend que le recourant, qui agit seul, s'en prend à sa détention pour insoumission en faisant essentiellement valoir qu'il ne peut pas rentrer en Algérie, il convient de ne pas se montrer trop formaliste et de retenir que les conditions de motivation de l'art. 42 al. 1 et 2 LTF sont remplies. Le recours est partant, sur le principe, recevable. Plusieurs conclusions et plusieurs griefs ne sont cependant pas admissibles, ainsi qu'il sera vu ci-après (cf. infra consid. 2 et 3).
2.
Il convient tout d'abord de préciser l'objet du litige. La partie recourante ne peut en effet pas prendre de conclusions ni formuler des griefs allant au-delà de cet objet (cf. <ref-ruling> consid. 4.4.2 p. 156 et les références citées; arrêt 2C_901/2016 du 24 mai 2017 consid. 3.1), ce qui semble échapper au recourant.
En l'occurrence, le litige porte uniquement sur la confirmation du 14 février 2020 par le Tribunal cantonal du placement du recourant en détention administrative pour insoumission pour un durée d'un mois, détention qui s'est déroulée entre le 30 décembre 2019 et le 29 janvier 2020.
Par conséquent, toutes les demandes (autorisation de travail, mise à zéro des poursuites, ordre que le procureur fédéral soit saisi du dossier) et critiques du recourant qui ne sont pas en lien avec la détention pour insoumission sont irrecevables dans le cadre du présent litige et ne seront, partant, pas examinées.
3.
3.1. Saisi d'un recours en matière de droit public, le Tribunal fédéral contrôle librement le respect du droit fédéral, qui comprend les droits de nature constitutionnelle (cf. art. 95 let. a et 106 al. 1 LTF), sous réserve des exigences de motivation figurant à l'<ref-law>. Aux termes de cet alinéa, le Tribunal fédéral n'examine la violation de droits fondamentaux que si ce grief a été invoqué et motivé par la partie recourante, c'est-à-dire s'il a été expressément soulevé et exposé de façon claire et détaillée (cf. <ref-ruling> consid. 2.4 p. 368 et les arrêts cités).
3.2. En l'espèce, en tant que le recourant se plaint de la violation de dispositions de la CEDH et de ses protocoles additionnels, ses critiques ne remplissent pas les exigences de motivation de l'<ref-law>. Le recourant se contente en effet de citer une série de dispositions, qui pour beaucoup n'ont même pas un lien ténu avec la cause (ainsi des articles de la Convention et des Protocoles relatifs aux ratifications par les Etats parties). Hormis le grief portant sur l'art. 6 CEDH et l'assistance judiciaire (cf. infra consid. 6), aucune critique en lien avec la CEDH et ses protocoles ne sera partant examinée.
4.
Le Tribunal fédéral statue s ur la base des faits établis par l'autorité précédente (<ref-law>). Il ne peut s'en écarter que si ceux-ci ont été constatés de façon manifestement inexacte ou en violation du droit au sens de l'<ref-law> (<ref-law>), et si la correction du vice est susceptible d'influer sur le sort de la cause (<ref-law>). La notion de manifestement inexacte correspond à celle d'arbitraire au sens de l'art. 9 Cst. (cf. <ref-ruling> consid. 2.2 p. 313).
5.
Le recourant dénonce un manque d'impartialité de la Présidente du Tribunal cantonal. A défaut d'un quelconque élément objectif à l'appui de cette critique, celle-ci n'a pas être examinée plus avant.
6.
Le recourant semble se plaindre de ne pas avoir bénéficié de l'aide d'un avocat d'office au cours de la procédure devant le Tribunal cantonal. Il cite l'art. 6 par. 3 let. c CEDH.
6.1. L'art. 6 par. 3 CEDH se réfère à "l'accusé" et concerne ainsi la procédure pénale. Le présent litige n'a pas pour objet une détention pénale, mais administrative. L'art. 6 CEDH n'est partant pas applicable (cf. arrêt 2C_816/2013 du 15 octobre 2013 consid. 3.2.1).
6.2. Le droit à l'assistance judiciaire découle toutefois également de l'art. 29 al. 3 Cst., et, en cas de privation de liberté, de l'art. 31 al. 2, 2e phrase Cst. (ATF <ref-ruling> consid. 3.3 p. 214; <ref-ruling> consid. 3.2.3 p. 100). L'art. 29 al. 3 Cst. confère au justiciable une garantie minimale, dont le Tribunal fédéral examine librement le respect (ATF <ref-ruling> consid. 3.2.1 p. 99).
Cette disposition conditionne notamment l'octroi de l'assistance judiciaire gratuite à l'existence de chances de succès dans la cause de celui qui réclame cette assistance (cf. <ref-ruling> consid. 1.2 p. 397; <ref-ruling> consid. 2.2.4 p. 218). Cette condition vaut également, sur le principe, en matière de détention administrative (ATF <ref-ruling> consid. 3.3.1 p. 214), excepté dans le cas particulier, non pertinent en l'espèce, des détentions Dublin (cf. <ref-ruling>). L'exigence selon laquelle la cause ne doit pas être dépourvue de chances de succès doit toutefois, en présence d'une privation de liberté d'une certaine intensité, respectivement d'une certaine durée, être relativisée. La jurisprudence admet ainsi que, lorsque la détention administrative dépasse trois mois, il faut en principe accorder au détenu qui le requiert un défenseur d'office (cf. ATF <ref-ruling> consid.3.2.3 p. 100 s.; arrêt 2C_675/2011 du 20 septembre 2011 consid. 3.2). Par ailleurs, lorsque une détention pour insoumission fait suite à une détention en vue du renvoi ou de l'expulsion atteignant déjà une durée de trois mois, il y a lieu, au vu des particularités de cette forme de détention, d'accorder l'assistance demandée par l'intéressé, déjà lors du premier examen - avec audition orale - de la détention. Par la suite, l'assistance sera accordée seulement si le cas soulève des questions de droit ou de fait d'une difficulté particulière (ATF <ref-ruling> consid. 3 et 4).
6.3. En l'occurrence, dans son arrêt, le Tribunal cantonal a considéré que la demande d'assistance judiciaire était sans objet, car le recours était dépourvu de chance de succès. Il a au surplus relevé que le recourant avait été assisté d'un conseil d'office devant le Tribunal des mesures de contrainte et que le cas ne soulevait pas de questions de droit ou de fait d'une difficulté particulière justifiant également la désignation d'un conseil d'office pour la procédure devant lui.
6.4. Il n'apparaît pas que cette argumentation méconnaîtrait les principes sus-exposés en matière d'assistance judiciaire et le recourant ne l'expose pas. Il est en particulier souligné que le recourant a bénéficié de l'aide d'un conseil d'office pour la procédure devant le Tribunal des mesures de contrainte, ce que l'intéressé ne conteste pas. Le Tribunal cantonal n'a partant pas violé le droit fédéral en rejetant la demande d'assistance judiciaire pour la procédure devant lui.
7.
Le recourant reproche, en substance, au Tribunal cantonal d'avoir confirmé sa mise en détention pour insoumission.
7.1. Selon l'art. 78 al. 1 LEI (RS 142.20), si l'étranger n'a pas obtempéré à l'injonction de quitter la Suisse dans le délai prescrit et que la décision entrée en force de renvoi ou d'expulsion ne peut être exécutée, en raison de son comportement, il peut être placé en détention afin de garantir qu'il quittera effectivement le pays, pour autant que les conditions de la détention au sens de l'art. 76 ne soient pas remplies et qu'il n'existe pas d'autre mesure moins contraignante permettant d'atteindre l'objectif visé.
Le but de la détention pour insoumission est d'inciter un étranger tenu de quitter la Suisse à changer de comportement lorsque, à l'échéance du délai de départ, l'exécution de la décision de renvoi entrée en force ne peut être assurée sans la coopération de l'étranger malgré les efforts des autorités (cf. <ref-ruling> consid. 2.1 p. 411; <ref-ruling> consid. 2.2.1 p. 107; <ref-ruling> consid. 2.2 p. 99). La détention pour insoumission apparaît ainsi comme une ultima ratio, dans la mesure où il n'existe plus d'autres mesures permettant d'aboutir à ce que l'étranger présent illégalement en Suisse soit renvoyé dans son pays (<ref-ruling> consid. 2.1 p. 411; arrêt 2C_639/2011 du 16 septembre 2011 consid. 3.1).
7.2. Conformément aux conditions fixées à l'art. 78 al. 1 LEI, il faut, pour qu'une détention pour insoumission soit ordonnée, qu'une décision de renvoi ou d'expulsion soit entrée en force, que la personne concernée ne s'y soit pas conformée dans le délai imparti et que l'exécution du renvoi ou de l'expulsion échoue en raison du comportement reprochable de l'intéressé (cf. arrêt 2C_1038/2018 du 7 décembre 2018 consid. 2.2). En outre, la détention en vue du renvoi (art. 76 LEI) ne doit plus être possible et il ne doit pas y avoir d'autres moyens moins contraignants pour atteindre le but visé (cf. arrêt 2C_1038/2018 du 7 décembre 2018 consid. 2.2). A noter que le but de la détention pour insoumission devient sans objet si une demande d'asile est formée durant la période de détention, dès lors que l'étranger a le droit de demeurer en Suisse jusqu'à la conclusion de la procédure d'asile (<ref-ruling> consid. 2.3 p. 412 s.).
7.3. La durée de la détention pour insoumission ne doit pas excéder, avec la détention en vue du renvoi et la détention en phase préparatoire, dix-huit mois (art. 78 al. 2 LEI et 79 al. 1 et 2 LEI; <ref-ruling> consid. 2.1 p. 411).
7.4. La détention pour insoumission doit en tous les cas respecter le principe de la proportionnalité, ce qui suppose d'examiner l'ensemble des circonstances pour déterminer si elle paraît appropriée, ainsi que nécessaire, et s'il existe un rapport raisonnable entre les moyens (la détention) et le but visé (le changement de comportement) (cf. <ref-ruling> consid. 2.1 p. 411; <ref-ruling> consid. 2.2.1 p. 107; <ref-ruling> consid. 2.2.2 p. 204; <ref-ruling> consid. 2.3.2 p. 97; <ref-ruling> consid. 2.2 p. 100). Le refus explicite de collaborer de la personne concernée est un indice important, mais d'autres éléments entrent aussi en compte (ATF <ref-ruling> consid. 2.2.2 p. 108; <ref-ruling> consid. 2.2.4 p. 205 s.). Ainsi, le comportement de l'intéressé, la possibilité qui lui est offerte de mettre concrètement lui-même fin à sa détention s'il coopère, ses relations familiales ou le fait qu'en raison de son âge, son état de santé ou son sexe, il mérite une protection particulière, peuvent aussi jouer un rôle (ATF <ref-ruling> consid. 2.2.2 p. 107 s.; <ref-ruling> consid. 2.3.2 p. 97; arrêts 2C_1038/2018 du 7 décembre 2018 consid. 2.3; 2C_984/2013 du 14 novembre 2013 consid. 3.2 et 3.4 et les arrêts cités).
7.5. En l'occurrence, le recourant a fait l'objet d'une première décision de renvoi le 24 avril 2012, qu'il n'a pas respectée. Le 5 novembre 2015, le Secrétariat d'Etat, rejetant sa demande d'asile, lui a à nouveau ordonné de quitter la Suisse. Cette décision, confirmée par le Tribunal administratif fédéral, est entrée en force. Le recourant n'a pourtant pas quitté la Suisse dans le délai imparti. Les deux premières conditions de l'art. 78 al. 1 LEI sont réunies.
7.6. Il faut donc se demander si la cause de la non-exécution de la décision de renvoi réside dans le comportement reprochable du recourant, ce que celui-ci conteste.
Il ressort de l'arrêt attaqué que les autorités algériennes reconnaissent le recourant comme étant un de leurs ressortissants. Par ailleurs, il résulte du dossier qu'en juin 2012, les autorités algériennes avaient fait savoir aux autorités suisses qu'elles étaient disposées à établir un laissez-passer en faveur du recourant (cf. <ref-law>). Il n'existait donc, à cette époque tout le moins, aucun empêchement autre que le refus de l'intéressé à un retour en Algérie.
Selon l'arrêt entrepris, en 2019, les autorités algériennes n'ont toutefois pas délivré de laissez-passer au recourant, malgré les demandes et efforts du Secrétariat d'Etat en ce sens (courriers des 14 mai, 29 mai et 5 juin 2019), ce qui a conduit à l'annulation des vols à destination d'Alger, prévus les 1er juin et 21 juin 2019. Il ressort également de l'arrêt attaqué que les autorités algériennes auraient, en avril 2018, demandé aux autorités suisses de surseoir à l'exécution du renvoi en raison de procédures pendantes contre le recourant.
Déduire de ces éléments que les autorités algériennes sont à l'origine de l'impossibilité d'exécuter le renvoi reviendrait toutefois à ignorer la déclaration écrite de 2012 figurant au dossier en faveur de l'octroi d'un laissez-passer. En outre et surtout, cela méconnaîtrait l'incidence du comportement du recourant sur l'état actuel de la situation. Le recourant n'a en effet jamais entrepris aucune démarche auprès des autorités de son pays pour se conformer à son obligation de départ de la Suisse. Il fait au contraire tout son possible pour ne pas quitter le pays. Il démultiplie notamment les demandes de réexamen du rejet de sa demande d'asile. Sur ce point, il est précisé que, contrairement à ce que soutient l'intéressé, aucune demande d'asile en cours ne fait obstacle à la présente mesure de détention pour insoumission, puisque le Secrétariat d'Etat a classé, sans décision formelle, la dernière demande de réexamen présentée (cf. <ref-law>). Le recourant s'est en outre inscrit à l'Université de Fribourg, démontrant ainsi qu'il n'a aucune intention de quitter la Suisse. Il a du reste, selon l'arrêt attaqué, renoncé à son projet de se rendre au Maroc. Outre que le recourant n'entreprend pas de démarches pour quitter la Suisse, il cumule les condamnations pénales, ce qui semble dissuader les autorités algériennes de délivrer le laissez-passer. On peut déduire de ces circonstances que le recourant est à l'origine de la situation actuelle de blocage et que sa collaboration rendrait le renvoi possible.
Ce point de vue est corroboré par le fait que, comme l'a relevé le Tribunal cantonal, les autorités algériennes délivrent en principe des laissez-passer à leurs ressortissants reconnus, ainsi que l'avait du reste déjà souligné le Tribunal fédéral dans le cadre de l'examen de la détention en phase préparatoire du recourant (arrêt 2C_1072/2015 du 21 décembre 2015 consid. 3.3, cf. également arrêt 2C_1038/2018 du 7 décembre 2018 consid. 3.2.2). Or, il n'y a pas lieu de penser qu'il en irait différemment en l'espèce si le recourant se montrait prêt à collaborer avec les autorités. On peut encore relever dans le même sens, même s'il faut apprécier ces déclarations avec retenue dès lors qu'elles ne sont pas étayées par des preuves écrites, que le Service cantonal a indiqué dans la présente procédure que les autorités algériennes seraient disposées à délivrer un laissez-passer au recourant.
En définitive, sur le vu de l'ensemble de ces éléments, on peut admettre, avec l'autorité précédente, que l'inexécution de la décision de renvoi est due au comportement reprochable du recourant.
7.7. L'art. 78 al. 1 LEI exige encore qu'une détention en vue du renvoi au sens de l'art. 76 LEI ne soit pas possible. Tel est le cas en l'occurrence. En effet, ainsi que l'a déjà relevé la jurisprudence, conformément à l'Accord conclu le 3 juin 2006 et entré en vigueur le 26 novembre 2007 entre le Conseil fédéral de la Confédération suisse et le Gouvernement de la République algérienne démocratique et populaire sur la circulation des personnes (RS 0.142.111.279), un retour forcé par vol spécial vers l'Algérie est exclu. Un retour forcé est possible par vol régulier uniquement, ce qui implique la collaboration de la personne concernée. Le refus du recourant de rentrer en Algérie constaté ci-avant, doublé de l'impossibilité d'organiser un vol spécial vers ce pays, exclut la détention en vue du renvoi au sens de l'art. 76 LEI (cf. art. 80 al. 6 let. a LEI; cf. arrêts 2C_26/2013 du 29 janvier 2013 consid. 3.2; 2C_624/2011 du 12 septembre 2011 consid. 2.3). Le Service cantonal était fondé, dans ces conditions, à envisager la détention pour insoumission comme ultima ratio pour faire changer le recourant de comportement.
7.8. Le recourant a été détenu administrativement du 15 juillet 2015 au 24 novembre 2015, puis du 4 mars 2019 au 23 juin 2019, soit environ 8 mois. Avec la détention pour insoumission litigieuse en l'espèce, le total est donc d'environ 9 mois, ce qui est en deçà du maximum de 18 mois prévu à l'art. 79 al. 2 LEI.
Il est souligné que les peines privatives de liberté en exécution de condamnations pénales n'entrent pas dans ce calcul, ce qui semble échapper au recourant.
7.9. Il reste à vérifier que la mesure prononcée respecte le principe de proportionnalité.
Le recourant, né en 1973, est arrivé en Suisse en 2006. Il lui a été demandé une première fois de quitter ce pays en 2012, ordre qu'il n'a pas respecté. En 2015, les autorités suisses lui ont à nouveau ordonné de quitter le territoire, ce que l'intéressé n'a pas fait. Depuis 2011, le recourant cumule les condamnations pénales (18 condamnations au 31 décembre 2019), y compris pour des faits graves (vol, tentative de lésions corporelles graves). Quoi qu'il en pense, il est seul responsable des détentions pénales qu'il subit à intervalles réguliers. Le recourant n'est pas intégré en Suisse. Il n'a, à teneur de l'arrêt attaqué, pas d'attaches familiales, sociales ou professionnelles dans ce pays. Par ailleurs, on ne voit pas qu'il y ait d'autres circonstances particulières ou un état de vulnérabilité qui rendrait la détention pour insoumission disproportionnée. Le recourant relève certes être homosexuel, mais n'explique nullement en quoi ce fait modifierait cette appréciation.
Le recourant refuse catégoriquement de retourner en Algérie. Il souligne encore dans son recours au Tribunal fédéral ne pas vouloir se rendre dans ce pays. Ce refus ne signifie pas que la détention pour insoumission n'est pas propre à atteindre son but. Il ne s'agit en effet que d'un élément à prendre en considération parmi l'ensemble des circonstances, car le contraire aboutirait au résultat que le maintien en détention serait d'autant moins justifié que la personne refuse avec force son renvoi (arrêt 2C_984/2013 du 14 novembre 2013 consid. 3.2 et les arrêts cités). En l'espèce, on ne saurait inférer à ce stade du refus du recourant que la détention pour insoumission litigieuse, qui est la première prononcée dans le but de faire changer le recourant de comportement, est vouée à l'échec.
En l'absence d'une quelconque collaboration de l'intéressé et sur le vu de l'ensemble des circonstances qui précèdent, il y a lieu de retenir que la détention litigieuse a respecté le principe de proportionnalité. C'est partant sans violer le droit fédéral que le Tribunal a confirmé la détention pour insoumission.
8.
Les considérants qui précèdent conduisent au rejet du recours, dans la mesure où il est recevable. Le recourant, qui succombe, a demandé l'octroi de l'assistance judiciaire (<ref-law>). Son recours était cependant d'emblée dénué de chances de succès, de sorte que cette requête doit être rejetée (cf. arrêt 2C_81/2019 du 29 janvier 2019 consid. 3). Au vu des circonstances de la cause, il se justifie toutefois de ne pas percevoir de frais pour la procédure fédérale (cf. <ref-law>). Il n'est pas alloué de dépens (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est rejeté dans la mesure où il est recevable.
2.
La demande d'assistance judiciaire est rejetée.
3.
Il n'est pas perçu de frais judiciaires.
4.
Le présent arrêt est communiqué au recourant, au Service de la population et des migrants, au Tribunal des mesures de contrainte et au Tribunal cantonal de l'Etat de Fribourg, Ie Cour administrative, ainsi qu'au Secrétariat d'Etat aux migrations.
Lausanne, le 15 avril 2020
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président : Seiler
La Greffière : Kleber