Faits:
A.
A.a. X._, ressortissant algérien, né 1970, alias Z._, originaire du Maroc, né en 1973, a été condamné à Genève entre août 2003 et février 2012 à quatorze reprises, essentiellement pour vol, infraction à la législation fédérale sur les étrangers et à la loi fédérale sur les stupéfiants. Le total des peines d'emprisonnement prononcées à son égard s'élève à plus de 50 mois.
Le 6 novembre 2003, l'Office fédéral des étrangers (devenu l'Office fédéral des migrations; ci-après: l'Office fédéral) a rendu à son encontre une décision d'interdiction d'entrée en Suisse valable jusqu'au 5 novembre 2013; X._ a fait l'objet d'une décision de renvoi prononcée le 30 avril 2009 par l'Office cantonal de la population du canton de Genève (ci-après: l'Office cantonal).
Libéré de sa détention pénale le 5 juillet 2012, il a été remis entre les mains des services de police, en vue de son refoulement par un vol réservé pour lui le jour même. X._ a refusé d'entrer dans l'avion, au motif qu'il aurait avalé une lame de rasoir et un coupe-ongles, ce qui s'est avéré inexact.
A.b. Le 6 juillet 2012, il a été placé en détention administrative. Cette détention a été prolongée jusqu'en décembre 2012.
Le 6 décembre 2012, l'intéressé a une nouvelle fois catégoriquement refusé de monter à bord d'un vol à destination d'Alger en vue de son refoulement sous escorte policière. Le 10 décembre 2012, l'officier de police a ordonné la détention pour insoumission de X._ pour une durée d'un mois, ce qu'a confirmé le Tribunal administratif de première instance du canton de Genève (ci-après: le Tribunal de première instance) le 13 décembre 2012, le recours de l'intéressé déposé contre ce jugement ayant été rejeté par la Chambre administrative de la Cour de justice de la République et canton de Genève (ci-après: la Cour de justice) le 10 janvier 2013. La détention pour insoumission a été régulièrement prolongée par le Tribunal de première instance :
- par jugement du 7 janvier 2013 jusqu'au 10 mars 2013, le recours interjeté contre ce jugement ayant été rejeté par la Cour de justice le 24 janvier 2013;
- par jugement du 7 mars 2013 jusqu'au 10 mai 2013;
- par jugement du 8 mai 2013 jusqu'au 8 juillet 2013;
- par jugement du 4 juillet 2013 jusqu'au 8 septembre 2013; la Cour de justice a rejeté, le 24 juillet 2013 le recours formé par X._ contre cette décision; celui-ci a ensuite recouru au Tribunal fédéral, qui l'a débouté par arrêt du 15 octobre 2013 (cause 2C_816/2013).
A.c. Depuis le 5 juillet 2012, X._ s'est constamment opposé à son renvoi en Algérie. Il a plusieurs fois indiqué souhaiter se rendre en France, auprès de sa famille, soutenant avoir été titulaire d'une carte de résident échue depuis 2007 qu'il souhaitait faire renouveler. Le 18 juillet 2012, les autorités françaises ont refusé une demande de réadmission de l'intéressé, au motif que celui-ci n'avait jamais bénéficié d'un titre de séjour en France. L'intéressé n'a en outre rien entrepris pour faciliter les démarches permettant son refoulement: il a refusé de monter à bord du vol du 6 décembre 2012 pour son retour sous escorte policière, a invoqué un prétexte pour ne pas rencontrer les autorités consulaires algériennes venues le voir en détention, a refusé de signer des documents présentés par l'Office cantonal, notamment en vue d'obtenir des informations concernant son état de santé. Il a fait preuve tout au long de la procédure d'une absence de collaboration, persistant à affirmer son refus de retourner en Algérie et posant des conditions irréalistes à un changement d'attitude. Le 13 août 2013, il a été transféré de Frambois au centre de détention de Zurich, dans la mesure où, malgré de nombreux avertissements, il avait semé le trouble dans l'établissement.
B.
Le 2 septembre 2013, l'Office cantonal a sollicité une nouvelle prolongation de la détention administrative de X._ jusqu'au 8 novembre 2013.
Par jugement du 4 septembre 2013, le Tribunal de première instance a admis la demande de prolongation de la décision administrative jusqu'au 16 septembre 2013 à 12h., ordonné la mise en liberté de l'intéressé à cette échéance et ordonné à l'Office cantonal de prendre dans l'intervalle les mesures de contrainte de substitution tendant à assigner à X._ un lieu de résidence dans le canton de Genève, avec prise de domicile dans un lieu d'accueil et à la fixation des modalités de présentation hebdomadaire auxquelles il devait se soumettre. Le Tribunal a ordonné à l'intéressé de se conformer auxdites mesures pour une durée de six mois dès leur mise en oeuvre. Tout en reconnaissant que les conditions de la détention pour insoumission existaient encore, les juges de première instance ont considéré qu'en regard de la détermination de X._ à ne pas retourner dans son pays d'origine, sa détention ne se justifiait plus au regard du principe de la proportionnalité, de sorte qu'il devait être libéré. Néanmoins, il existait un intérêt public sérieux à ce que le départ de l'intéressé, qui avait un lourd passé pénal et ne disposait ni d'un titre de séjour ni de moyens d'existence légaux, soit assuré, ce qui justifiait les mesures de substitution.
Statuant sur recours de l'Office cantonal, la Cour de justice a, par arrêt du 20 septembre 2013, admis celui-ci, annulé le jugement du 4 septembre 2013 et prolongé la détention administrative de X._ pour une durée de deux mois, soit jusqu'au 2 novembre 2013. Les juges cantonaux ont considéré que X._ ne faisait état d'aucune circonstance nouvelle depuis leurs arrêts des 10 janvier et 24 juillet 2013 propre à rendre sa détention injustifiée. Le seul refus systématique de l'intéressé de collaborer à son renvoi, voire de l'empêcher par différents moyens, ne rendait pas la détention disproportionnée et aucune autre mesure moins incisive ne permettait d'assurer la présence physique de l'intéressé le jour où un vol pourrait être organisé à destination de l'Algérie.
C.
A l'encontre de l'arrêt du 20 septembre 2013, X._ forme un recours en matière de droit public au Tribunal fédéral en concluant à l'annulation de l'arrêt attaqué et au prononcé de sa mise en liberté immédiate assortie des mesures de contrainte de substitution visant à son assignation à résidence dans le canton de Genève, avec prise de domicile dans un lieu d'accueil préalablement réservé à son attention et à sa soumission à une obligation de se présenter chaque semaine auprès d'une autorité désignée et d'en fixer les modalités. Subsidiairement, il demande l'annulation de l'arrêt attaqué et le renvoi de la cause à l'autorité cantonale pour nouvelle décision. Il sollicite par ailleurs l'octroi de l'assistance judiciaire.
L'Office cantonal a renoncé à se prononcer, se référant à l'arrêt attaqué. L'Office fédéral ne s'est pas non plus déterminé. La Cour de justice a indiqué (tardivement) qu'elle renonçait à formuler des observations.
D.
Le 31 octobre 2013, le Tribunal de première instance a autorisé la prolongation de la détention administrative du recourant jusqu'au 2 janvier 2014.

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. 1 p. 133). Pour déterminer si, au moment où il se prononce, les conditions de recevabilité sont réunies, le Tribunal fédéral peut prendre en compte des faits postérieurs à l'acte attaqué; il s'agit d'exceptions à l'interdiction des faits nouveaux prévue à l'<ref-law> (cf. <ref-ruling> consid. 3.3 p. 500; arrêt 2C_825/2011 du 25 avril 2012 consid. 1).
1.1. En matière de mesures de contrainte, le recours en matière de droit public est ouvert (<ref-law>; arrêt 2C_364/2013 du 1er mai 2013 consid. 3 et la jurisprudence citée). 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. 4.2 p. 299 et les arrêts cités). Le Tribunal fédéral fait 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.1 p. 208; <ref-ruling> consid. 1.1 p. 103).
Le Tribunal fédéral a récemment jugé que, lorsque la détention administrative se poursuit sur la base d'une nouvelle décision, laquelle repose sur les mêmes bases légales que la décision attaquée, et qu'il est difficile, voire impossible en raison de la durée de la procédure cantonale, que la Cour de céans se prononce avant que la question perde de son actualité, l'intéressé garde un intérêt digne de protection à l'annulation de la décision attaquée pour soulever des questions de principe dont la solution s'impose pour des raisons d'intérêt public (<ref-ruling> consid. 1.2.3 p. 210 s.).
En l'espèce, l'arrêt attaqué a prolongé la détention litigieuse du recourant du 9 septembre 2013 jusqu'au 2 novembre 2013. Le recourant se trouve actuellement toujours en détention pour insoumission, mais sur la base d'un nouveau jugement du Tribunal de première instance du 31 octobre 2013, prolongeant la détention jusqu'au 2 janvier 2014. Partant, le recours déposé le 23 octobre 2013 à l'encontre de l'arrêt du 20 septembre 2013 a, a priori, perdu son intérêt actuel. Toutefois, il se justifie en l'espèce de renoncer à l'exigence de l'intérêt actuel, car la présente détention du recourant repose sur le même fondement juridique que celui sur la base duquel l'arrêt attaqué a été rendu. S'ajoute à cela que, compte tenu de la durée résiduelle de la prolongation prononcée par la Cour de justice dans l'arrêt attaqué, il était difficile voire impossible que le Tribunal fédéral se prononce avant son échéance. Enfin, la question litigieuse de la proportionnalité de la mesure est opposable à tous les cas de détention pour insoumission et revêt donc un intérêt public. Partant, il convient d'admettre que les conditions de l'<ref-law> sont réalisées en l'espèce.
1.2. Pour le surplus, 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) et déposé dans le délai (<ref-law>) et les formes prévues par la loi (<ref-law>), le recours est en principe recevable.
2.
Le recourant se plaint d'une violation de l'art. 19 de la loi cantonale genevoise sur la procédure administrative du 12 septembre 1985 (RS/GE E 5 10; ci-après: LPA) et de son droit d'être entendu, reprochant à la Cour de justice de ne pas avoir donné suite à ses demandes tendant à l'audition de trois médecins, ainsi qu'à la mise en oeuvre d'une expertise médicale et psychiatrique, alors qu'elle a retenu que ses prétendues tentatives de suicide n'étaient pas démontrées et que son état de santé est un point fondamental à prendre en compte dans le cadre de la prolongation de sa détention.
2.1. Lorsque le recourant se plaint d'une violation de l'art. 19 LPA, il perd de vue que, sauf exceptions non réalisées en l'espèce (cf. art. 95 let. c, d et e LTF), la violation du droit cantonal y compris de procédure ne constitue pas un motif de recours au Tribunal fédéral (<ref-law> a contrario; arrêts 2C_993/2013 du 28 octobre 2013 consid. 3; 2C_116/2011 du 29 août 2011 in SJ 2011 I p. 405, consid. 3.1). Dans la mesure où le recourant ne fait pas valoir que le droit de procédure aurait été appliqué arbitrairement ou contrairement à d'autres droits constitutionnels, sa critique n'est donc pas recevable (<ref-law>; cf. <ref-ruling> consid. 2.2 p. 69; <ref-ruling> consid. 1.3.1 p. 68).
2.2. Reste le grief de la violation du droit d'être entendu qui, compte tenu de son caractère formel, doit être examiné avant le fond (cf. <ref-ruling> consid. 3 p. 191).
2.2.1. Le droit d'être entendu, tel qu'il est garanti par l'art. 29 al. 2 Cst., comprend notamment le droit pour l'intéressé d'obtenir qu'il soit donné suite à ses offres de preuves pertinentes (<ref-ruling> consid. 9.2 p. 48 s. et les références citées). Ce droit suppose que le fait à prouver soit pertinent, que le moyen de preuve proposé soit nécessaire pour constater ce fait et que la demande soit présentée selon les formes et délais prescrits par le droit cantonal (<ref-ruling> consid. 5b/bb p. 505). Par ailleurs, cette garantie constitutionnelle n'empêche pas l'autorité de mettre un terme à l'instruction lorsque les preuves administrées lui ont permis de former sa conviction et que, procédant d'une manière non arbitraire à une appréciation anticipée des preuves qui lui sont encore proposées, elle a la certitude qu'elles ne pourraient l'amener à modifier son opinion (<ref-ruling> consid. 4.3.2 p. 376; <ref-ruling> consid. 5.3 p. 236).
2.2.2. L'arrêt attaqué explique pour quels motifs il n'a pas été donné suite aux mesures d'instruction proposées par le recourant et pourquoi l'état de santé de celui-ci ne justifiait pas sa libération. Les juges ont souligné que le recourant n'avait invoqué aucune circonstance nouvelle en lien avec sa santé par rapport à la situation qui prévalait lorsque la Cour de justice avait déjà examiné la cause, à savoir le 10 janvier 2013 et le 24 juillet 2013. Le recourant n'avait en outre fourni aucun nouveau certificat médical par rapport à ceux produits auparavant et qui avaient alors été pris en considération; il aurait pourtant eu l'occasion d'étayer depuis plusieurs mois les troubles psychiques qu'il alléguait, ce qu'il n'avait pas fait. En outre, les tentatives de suicide dont l'intéressé avait déjà fait état le 7 mars 2013 n'étaient aucunement prouvées.
On ne voit pas que cette appréciation anticipée des preuves serait arbitraire. Au demeurant, il appartenait au recourant de le démontrer (<ref-law>) ou à tout le moins d'expliquer pourquoi il n'avait pas produit de nouveaux certificats des médecins dont il demandait l'audition, alors qu'il a été retenu qu'il en aurait eu l'occasion depuis des mois et dans quelle mesure il serait insoutenable de retenir que les tentatives de suicide alléguées n'étaient pas démontrées. Il ne le fait nullement, son argumentation se limitant à dire que son état de santé était un point fondamental qui s'opposait à la prolongation de sa détention. En pareilles circonstances, le Tribunal fédéral ne dispose d'aucun élément tangible permettant de retenir une violation du droit d'être entendu au motif que la Cour de justice n'aurait pas donné suite aux offres de preuves du recourant en lien avec son état de santé.
3.
Sur le fond, le recourant se prévaut d'une violation du principe de la proportionnalité et de l'art. 78 LEtr. Il soutient que l'approche de la Cour de justice revient à vider de son sens ce principe, car elle suppose d'attendre la fin de la période maximale de détention pour insoumission pour savoir si celle-ci a porté ses fruits.
3.1. Selon l'art. 78 al. 1 LEtr, si l'étranger n'a pas obtempéré à l'injonction de quitter la Suisse dans le délai prescrit et que la décision exécutoire 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 en vue du renvoi ou de l'expulsion ne soient pas remplies et qu'il n'existe pas d'autre mesure moins contraignante susceptible de conduire à l'objectif visé. Le but de la détention pour insoumission est de pousser 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. art. 78 LEtr; <ref-ruling> consid. 2.2.1 p. 107). La détention pour insoumission apparaît 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 puisse être renvoyé dans son pays (arrêt 2C_26/2013 du 29 janvier 2013 consid. 3.1).
3.2. Selon la jurisprudence, la détention pour insoumission doit toujours respecter le principe de la proportionnalité, ce qui suppose d'examiner l'ensemble des circonstances pour déterminer si elle paraît appropriée et nécessaire (cf. <ref-ruling> consid. 2.2.1 p. 107; <ref-ruling> consid. 2.3.2 p. 97), étant précisé que plus la détention se prolonge, plus les exigences relatives à la proportionnalité sont accrues (Minh Son Nguyen, Les renvois et leur exécution en droit suisse, in Les renvois et leur exécution, Berne 2011, p. 115 ss, 183). Le refus explicite de collaborer de la personne concernée est un indice important, mais d'autres éléments entrent aussi en compte (<ref-ruling> consid. 2.2.2 p. 108; <ref-ruling> consid. 2.2.4 p. 205 s. confirmé notamment in arrêt 2C_538/2010 du 19 juillet 2010 consid. 4.3.1). 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 (arrêts 2C_639/2011 du 16 septembre 2011 consid. 3.1; 2C_624/2011 du 12 septembre 2011 consid. 2.1; 2C_936/2010 du 24 décembre 2010 consid. 1.3).
Dans l'<ref-ruling>, le Tribunal fédéral a considéré comme disproportionné le maintien en détention pour insoumission d'un étranger déjà détenu depuis plus de 18 mois, dès lors qu'il persistait dans son refus d'être renvoyé, de sorte qu'il était probable qu'il ne change pas d'attitude. Dans cette affaire, d'autres circonstances que l'attitude obstructive du recourant ont toutefois joué un rôle: l'étranger concerné avait des attaches familiales en Suisse, dont un enfant sur lequel il avait un droit de visite, et aucun antécédent pénal, éléments dont il a été tenu compte en sa faveur (cf. <ref-ruling> consid. 2.3.2). En outre, la législation alors en vigueur prévoyait une durée maximale de détention de 24 mois, alors que le droit européen imposait une durée maximale de 18 mois, ce qui a également influencé l'appréciation de la proportionnalité (cf. <ref-ruling> consid. 2.3.3). Dans un arrêt antérieur (ATF <ref-ruling>) dont l'<ref-ruling> n'indique pas s'écarter, mais régler un contexte différent (cf. dernier arrêt précité consid. 2.3.2 p. 108), il a été jugé que le refus constant de collaborer du détenu ne permet à lui seul pas d'en déduire que la détention pour insoumission n'est plus propre à atteindre son but; il ne s'agit que d'un élément à prendre en considération parmi l'ensemble des circonstances sous peine d'aboutir au résultat que le maintien en détention serait d'autant moins justifié que la personne refuse avec force son renvoi (ATF <ref-ruling> consid. 2.2.4 p. 206, qui confirme l'ATF <ref-ruling> consid. 2.3.2 in fine).
3.3. En l'espèce, le recourant a fait l'objet d'une interdiction d'entrée en Suisse du 6 novembre 2003 qui est arrivée à expiration le 5 novembre 2013, ce qui ne l'a pas empêché de résider sur le territoire suisse et d'y commettre de nombreux délits. Entre 2003 et jusqu'au moment de sa mise en détention administrative en 2012, il a été condamné quatorze fois par la justice genevoise notamment pour vol par métier et en bande. Les peines prononcées à son encontre n'ont pas été négligeables, puisqu'il a été condamné une fois à 8 mois d'emprisonnement et 4 fois à six mois. Placé en détention administrative en vue de son renvoi le 6 juillet 2012 après avoir une première fois refusé de monter dans un vol en vue de son refoulement à destination d'Alger, il a réitéré son refus le 6 décembre 2012, et a été placé depuis lors en détention pour insoumission. Durant toute sa détention, le recourant a toujours refusé de collaborer, persistant dans son refus de retourner en Algérie, posant des conditions irréalistes à un éventuel changement d'attitude. Ces éléments permettent d'en conclure que le recourant remplissait à l'évidence, tant en décembre 2012 qu'au moment du prononcé de l'arrêt attaqué, les conditions d'une détention pour insoumission au sens de l'art. 78 LEtr, ce que celui-ci ne conteste du reste pas.
3.4. Encore faut-il se demander si la détention pour insoumission demeure conforme au principe de la proportionnalité. Selon la jurisprudence précitée (cf. supra consid. 3.1), cet examen suppose de tenir compte de l'ensemble des circonstances, parmi lesquelles figurent la durée de la détention déjà accomplie, la persistance du détenu à ne pas collaborer, ses relations familiales, son âge, son état de santé et ses antécédents.
3.4.1. Il découle de l'art. 79 al. 1 et al. 2 let. a LEtr que, si la personne concernée ne coopère pas avec l'autorité compétente, la durée maximale de la détention, qui comprend notamment la détention en vue du renvoi et la détention pour insoumission, ne peut excéder au total 18 mois. Le recourant a été placé en détention administrative le 6 juillet 2012 et est en détention pour insoumission depuis le 10 décembre 2012; il devra donc être libéré au plus tard le 5 janvier 2014. Compte tenu de la durée de la détention déjà accomplie, l'examen de la proportionnalité est soumis à des exigences accrues et suppose ainsi un examen attentif des éléments en faveur de la personne détenue (cf. <ref-ruling> consid. 2.2.2 p. 108).
3.4.2. S'agissant de la situation familiale du recourant, il n'a pas été constaté, et celui-ci ne l'a du reste pas allégué, qu'il aurait de la famille proche en Suisse, qu'il soit sur le point de se marier ou qu'un enfant soit né pendant sa détention et vive dans le pays, à savoir des éléments qui pourraient jouer un rôle en sa faveur sous l'angle de la proportionnalité de sa détention. Il soutient avoir de la famille en France qu'il souhaiterait pouvoir rejoindre. Cet argument n'est pas déterminant. En effet, les autorités suisses ont déclaré qu'elles ne seraient pas opposées à laisser le recourant se rendre en France à condition qu'il dispose d'une autorisation pour pénétrer sur le territoire français; elles ont d'ailleurs adressé une demande de réadmission dans ce pays le 18 juillet 2012, qui a été refusée par la France le même jour. Le fait que le recourant ait cherché par la suite et jusqu'à présent sans succès à régulariser sa situation en France, par l'intermédiaire de sa soeur, ne justifie donc pas de renoncer à sa détention ni à son renvoi en Algérie, d'où il pourrait parfaitement se rendre en France pour rejoindre sa famille si cet Etat finissait par accepter qu'il séjourne sur son territoire.
3.4.3. Le recourant a régulièrement invoqué son état de santé pour s'opposer à la prolongation de sa détention. Les autorités saisies ont chaque fois examiné cette question, notamment la Cour de justice, non seulement dans l'arrêt attaqué, mais aussi dans deux décisions, la première du 11 janvier 2013 et la seconde du 24 juillet 2013, le recours formé contre cette dernière décision ayant du reste été rejeté par le Tribunal fédéral le 15 octobre 2013 (cause 2C_816/2013). Or, il a été constaté dans l'arrêt attaqué, d'une manière qui lie la Cour de céans (<ref-law>), que le recourant n'avait invoqué dans la présente procédure aucune circonstance notablement nouvelle par rapport à la situation déjà examinée par les juges précédemment. Ainsi, le recourant n'a produit aucun élément propre à démontrer que les affections ORL qui le touchent depuis longtemps l'empêcheraient de prendre l'avion. Les troubles psychiques dont il souffre et qui ont déjà été jugés compatibles avec une privation de liberté n'ont été étayés par aucun rapport médical récent et le certificat du Dr. A._ du 22 novembre 2012 ne permet nullement de considérer que la détention administrative du recourant lui serait devenue gravement préjudiciable. Quant aux tentatives de suicide alléguées, elles ne sont pas démontrées et l'intéressé en avait déjà fait état lors d'une audience le 7 mars 2013.
Comme déjà indiqué, le recourant ne remet pas en cause ces constatations. Il ne soutient nullement devant le Tribunal fédéral que son état de santé aurait été arbitrairement évalué et qu'il souffrirait d'affections incompatibles avec la prolongation de sa détention; il ne donne aucun détail sur les tentatives de suicide qu'il allègue ni ne prétend que ce serait de manière insoutenable que les juges les auraient mises en doute. Il reproche seulement, de manière infondée, à la Cour de justice, d'avoir violé son droit d'être entendu en ne donnant pas suite à ses offres de preuves tendant à établir son état de santé, mais sans aucun détail à ce sujet (cf. supra consid. 2.2.2).
Par conséquent, sur la base des faits constatés dans l'arrêt attaqué, aucun élément probant ne permet d'admettre que la prolongation de la détention pour insoumission litigieuse serait de nature à atteindre le recourant dans sa santé ou à le mettre en danger.
3.4.4. On peut ajouter que le recourant est né en 1970. Il n'est donc pas dans une tranche d'âge incompatible avec son maintien en détention. Ses antécédents pénaux sont lourds (14 condamnations prononcées sur une période de 11 ans, portant sur des peines privatives de liberté totalisant plus de 50 mois d'emprisonnement); il y a donc un intérêt public à tout tenter pour permettre l'exécution de son renvoi.
3.4.5. Quant à l'attitude du recourant, elle n'a pas changé durant toute la période pendant laquelle il a été détenu pour insoumission. Il persiste dans une opposition à toute démarche visant à son renvoi et refuse ostensiblement de coopérer. Le litige revient ainsi à se demander si ce seul élément justifierait, sous l'angle de la proportionnalité, de libérer le recourant au motif qu'il est concevable que celui-ci poursuive dans cette attitude d'obstruction systématique durant les deux mois pendant lesquels sa détention administrative peut encore se poursuivre avant d'arriver au terme légal (cf. supra consid. 3.4.1).
Il convient de répondre à cette question par la négative. En effet, le refus de collaborer de l'étranger qui doit être renvoyé est une condition de la détention pour insoumission. Il apparaît donc paradoxal qu'un détenu puisse être libéré, parce qu'il continue de remplir la condition justifiant sa détention sur la base de l'art. 78 LEtr. A cela s'ajoute que, si l'on admet, sous l'angle de la proportionnalité, qu'il se justifie de libérer un détenu au seul motif qu'il continue à s'opposer à son renvoi dès lors qu'il ne lui reste que quelques mois de détention, on fait perdre tout sens à la durée maximale de la détention fixée à l'art. 79 LEtr, qui prévoit du reste que le refus de coopérer de la personne concernée justifie de prolonger la durée maximale de détention de douze mois (cf. art. 79 al. 2 let. a LEtr). Il convient de préciser que cette durée maximale, qui a été réduite de 24 à 18 mois, est désormais conforme à celle prévalant en droit européen (cf. <ref-ruling> consid. 2.3.3 p. 110). Quant à l'argument selon lequel le renvoi ne pourra de toute manière pas être exécuté, car l'intéressé va persévérer dans son comportement, de sorte que l'objectif visé par la détention devient irréalisable, il constitue une prime à l'obstruction, car il impose de libérer les détenus les plus déterminés à ne pas se soumettre, ce qui a déjà été souligné par la jurisprudence (cf. supra consid. 3.2 in fine). Il ne faut enfin pas perdre de vue qu'il suffirait au recourant de changer de comportement et d'accepter de monter dans un vol de retour pour l'Algérie, qui pourrait être organisé rapidement, pour mettre fin à la mesure de privation de liberté qu'il conteste.
Quant à la possibilité de mesures moins incisives (art. 74 LEtr), on ne voit pas qu'elles s'imposent. Comme l'a relevé à juste titre la Cour de justice, de telles mesures ne sont pas de nature à assurer la présence physique du recourant qui n'a pas d'attache en Suisse le jour où un vol pourra être organisé à destination de l'Algérie. A cela s'ajoute le risque que l'intéressé fait courir à l'ordre et à la sécurité publics s'il est libéré, compte tenu de ses graves antécédents pénaux, ce qui plaide pour le maintien de la mesure de détention (cf. arrêt 2C_866/2011 du 15 novembre 2011 consid. 5.4).
3.4.6. En résumé, on se trouve en présence d'un étranger détenu sur la base de l'art. 78 LEtr et qui ne peut se prévaloir d'aucune circonstance en sa faveur qui justifierait de renoncer à la prolongation de sa détention pour insoumission, si ce n'est la persistance dans son refus de collaborer à son renvoi. Dans un tel cas, même s'il convient d'apprécier la proportionnalité avec d'autant plus de vigilance que l'on arrive au terme de la durée maximale de la détention prévue par la loi, la seule probabilité que le détenu sur la base de l'art. 78 LEtr continue à refuser de collaborer ne suffit pas à mettre fin à la détention pour insoumission. Cette solution confirme en cela la jurisprudence rendue dans l'<ref-ruling>.
Dans ces circonstances, le recours doit être rejeté dans la mesure de sa recevabilité.
4.
Dès lors que le jugement du Tribunal de première instance prévoyait de ne pas prolonger la détention du recourant, contrairement à l'arrêt de la Cour de justice, il convient d'admettre que celui-ci pouvait conclure que son recours n'était pas d'emblée dépourvu de chances de succès, de sorte qu'il convient d'admettre la demande d'assistance judiciaire (<ref-law>).
Il ne sera donc pas perçu de frais (<ref-law>). Me Arnaud Moutinot sera désigné comme avocat d'office du recourant pour la procédure fédérale et ses honoraires, fixés par la Cour de céans, seront supportés par la Caisse du Tribunal fédéral (<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 admise. Me Arnaud Moutinot est désigné comme avocat d'office du recourant et une indemnité de 2'000 fr. lui est allouée à titre d'honoraires, à payer par la caisse du Tribunal fédéral.
3.
Il n'est pas perçu de frais judiciaires.
4.
Le présent arrêt est communiqué au mandataire du recourant, à l'Office cantonal de la population du canton de Genève, au Tribunal administratif de première instance du canton de Genève et à la Cour de justice de la République et canton de Genève, Chambre administrative, en section, ainsi qu'à l'Office fédéral des migrations.
Lausanne, le 14 novembre 2013
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: Zünd
La Greffière: McGregor