Faits:
A.
X._, ressortissant algérien, né en 1970, séjourne à Genève depuis le mois de juillet 2003. Dépourvu de pièce d'identité et sans domicile fixe, il n'a jamais sollicité l'octroi d'une autorisation de séjour.
Entre 2003 et 2012, l'intéressé a été condamné pénalement à treize reprises, essentiellement pour vol, infraction à la loi fédérale du 16 décembre 2005 sur les étrangers (LEtr; RS 142.20) et à la loi fédérale sur les stupéfiants et les substances psychotropes du 3 octobre 1951 (LStup; RS 812.121). Le 6 novembre 2003, l'Office fédéral des migrations a rendu à son encontre une décision d'interdiction d'entrée en Suisse valable jusqu'au 5 novembre 2013 et il 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 de la population).
X._, qui s'est constamment opposé à son renvoi en Algérie, a été placé en détention administrative pour insoumission, au sens de l'art. 78 LEtr, le 6 juillet 2012. Cette détention a été prolongée à six reprises par le Tribunal administratif de première instance du canton de Genève (ci-après: le Tribunal administratif de première instance) entre le 3 septembre 2012 et le 8 mai 2013.
B.
Le 2 juillet 2013, l'Office cantonal de la population a sollicité une nouvelle prolongation de la détention administrative de X._. A l'issue de son audience du 4 juillet 2013, au cours de laquelle l'intéressé, assisté par son conseil d'office, Me Arnaud Moutinot, a été entendu, le Tribunal administratif de première instance a admis la demande de prolongation de la détention administrative de X._ pour une durée de deux mois, soit jusqu'au 8 septembre 2013.
Saisie d'un recours dirigé contre le jugement précité du Tribunal administratif de première instance du 4 juillet 2013, la Cour de justice, Chambre administrative, du canton de Genève (ci-après: la Cour de justice) l'a rejeté, par arrêt du 24 juillet 2013. Elle a retenu, en substance, que le fait que X._ n'ait pu s'entretenir avec son avocat que pendant dix minutes avant le début de l'audience du 4 juillet 2013 devant le Tribunal administratif de première instance ne violait pas les garanties tirées du droit d'être entendu en procédure judiciaire, que la durée et le principe de la détention ordonnée respectaient le principe de proportionnalité et que les conditions de détention de X._, notamment au regard du partage de sa cellule à la maison d'arrêt de Favra avec un fumeur, ne prêtaient pas le flanc à la critique.
Le 2 septembre 2013, l'Office cantonal de la population a sollicité une nouvelle prolongation de la détention administrative de X._ pour une durée de deux mois, soit jusqu'au 8 novembre 2013. Saisie d'un recours interjeté par l'Office cantonal de la population contre l'arrêt du Tribunal administratif de première instance du 4 septembre 2013, la Cour de justice l'a admis et a prolongé la détention administrative de X._ jusqu'au 2 novembre 2013.
C.
Par acte du 13 septembre 2013, X._ forme un " recours de droit public " auprès du Tribunal fédéral dans lequel il conclut à l'annulation de l'arrêt de la Cour de justice du 24 juillet 2013, au prononcé de sa mise en liberté immédiate et à la constatation de l'illicéité de ses conditions de détention. Il demande par ailleurs l'assistance judiciaire. L'intéressé se plaint de n'avoir pas pu bénéficier du temps nécessaire à la préparation de sa défense et d'avoir été incarcéré avec un fumeur alors qu'il souffre d'asthme.
Persistant dans les considérants et le dispositif de l'arrêt attaqué, la Cour de justice n'a pas déposé de réponse, à l'instar de l'Office cantonal de la population. L'Office fédéral des migrations n'a pas présenté d'observations.

Considérant en droit:
1.
1.1. En matière de mesures de contrainte, le recours en matière de droit public est en principe ouvert (<ref-law>; arrêt 2C_364/2013 du 1er mai 2013 consid. 3 et la jurisprudence citée).
1.2. L'<ref-law> fait dépendre la qualité pour former un recours en matière de droit public notamment de la condition que le recourant ait un intérêt digne de protection à l'annulation ou à la modification de la décision attaquée (let. c). Le recourant doit ainsi avoir un intérêt pratique et actuel à obtenir l'annulation de la décision entreprise, intérêt qui doit exister non seulement au moment du dépôt du recours, mais encore au moment où l'arrêt est rendu (<ref-ruling> consid. 2.1 p. 41 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. 103; arrêt 2C_598/2013 du 22 juillet 2013 consid. 1.1, destiné à la publication). 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 (arrêt 2C_598/2013 du 22 juillet 2013 consid. 1.2.3, destiné à la publication).
En l'espèce, la prolongation litigieuse, prononcée le 4 juillet 2013, est arrivée à échéance le 8 septembre 2013. Le recourant se trouve toujours en détention, mais sur la base d'une nouvelle décision de la Cour de justice qui, le 20 septembre 2013, a prolongé sa détention de deux mois jusqu'au 2 novembre 2013. Cette nouvelle décision constitue le seul titre qui justifie actuellement la détention du recourant. Au moment du dépôt de son recours au Tribunal fédéral le 13 septembre 2013, le recourant n'avait donc a priori plus d'intérêt actuel à s'en prendre à l'arrêt attaqué. Toutefois, il se justifie en l'espèce de renoncer à l'exigence de l'intérêt actuel. En effet, la détention actuelle du recourant est fondée sur les mêmes bases légales que celle qui fait l'objet du présent recours. S'ajoute à cela que la durée de la prolongation est réduite, de sorte qu'il était difficile que le Tribunal fédéral se prononce avant son échéance. Enfin, s'agissant d'une cause générale, opposable à tous les cas de détention en vue de renvoi, elle revêt un intérêt public. Le recourant a donc bien un intérêt digne de protection à l'annulation de la décision attaquée.
1.3. 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, bien que mal intitulé, est en principe recevable.
2.
Le recourant a requis l'apport du dossier cantonal. Tant la Cour de justice que l'Office cantonal de la population ont déposé leurs dossiers, en application de l'<ref-law>, de sorte que la réquisition d'instruction du recourant a été satisfaite.
3.
3.1. Le recourant soutient en premier lieu qu'il n'a pas bénéficié du temps nécessaire pour la préparation de l'audience du 4 juillet 2013 devant le Tribunal administratif de première instance, puisqu'il n'a pu communiquer oralement avec son avocat que pendant dix minutes avant le début de cette audience. Le dossier de la cause n'ayant été remis à son conseil que 24 heures avant l'audience, celui-ci devait, selon le recourant, pouvoir partir de l'idée, compte tenu du volume et de la complexité de l'affaire, qu'il pourrait conférer avec son client depuis le début de l'entretien, à 14.00 h., jusqu'à l'ouverture de l'audience, à 15.30 h. Il invoque une violation de l'art. 6 par. 3 let. b de la Convention européenne de sauvegarde des droits de l'homme et des libertés fondamentales du 4 novembre 1950 (CEDH; RS 0.101) selon lequel tout accusé a le droit de disposer du temps et des facilités nécessaires à la préparation de sa défense et se prévaut également des garanties constitutionnelles tirées du droit d'être entendu en procédure judiciaire au sens des art. 29 al. 2 et 30 al. 1 Cst.
3.2.
3.2.1. L'art. 6 par. 1 CEDH donne à toute personne le droit à ce que sa cause soit entendue équitablement, publiquement et dans un délai raisonnable, par un tribunal indépendant et impartial établi par la loi, qui décidera soit de contestations sur ses droits et obligations de caractère civil, soit du bien-fondé de toute accusation en matière pénale dirigée contre elle. Une décision relative au séjour d'un étranger ou à son expulsion ne concerne ni un droit de caractère civil, ni une accusation en matière pénale au sens de l'art. 6 par. 1 CEDH (<ref-ruling> consid. 4.4.2 p. 133 s. et les références citées).
Le fait que le recourant soit détenu administrativement ne suffit pas à conférer au litige la qualité de droit de caractère pénal. En effet, le recourant n'est pas détenu en qualité d'accusé d'un crime ou d'un délit, mais au titre d'une mesure administrative visant à faciliter un renvoi pour lequel il refuse de coopérer. L'art. 6 par. 1 CEDH fait d'ailleurs expressément mention d'un accusé, soit d'un justiciable prévenu d'une infraction pénale (cf. arrêt 2C_66/2013 du 7 mai 2013 consid. 3.4). Cette disposition ne trouve donc pas application dans le cas d'espèce.
3.2.2. 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é de prendre connaissance du dossier, de s'exprimer sur les éléments pertinents avant qu'une décision ne soit prise touchant sa situation juridique, de produire des preuves pertinentes, d'obtenir qu'il soit donné suite à ses offres de preuves pertinentes, de participer à l'administration des preuves essentielles ou à tout le moins de s'exprimer sur son résultat, lorsque cela est de nature à influer sur la décision à rendre (<ref-ruling> consid. 3.2 p. 270 s.).
Selon l'art. 81 al. 1 LEtr, les cantons veillent à ce que la personne en détention puisse s'entretenir et correspondre avec son mandataire. Le représentant doit être avisé de la tenue de l'audience devant le juge de la détention, afin qu'il puisse y prendre part aux côtés de son mandant ou le conseiller préalablement. Si l'étranger n'est pas représenté devant le juge de la détention, parce que les autorités n'ont rien entrepris pour permettre un contact avec son mandataire, respectivement parce que son avocat n'a pas été informé de la mise en détention ou de son maintien, il y a violation du droit d'être entendu (cf. arrêts 2C_675/2011 du 20 septembre 2011 consid. 3.2; 2C_131/2011 du 25 février 2011 consid. 2.4.1; 2C_128/2009 du 30 mars 2009 consid. 2).
Il s'ensuit que l'intéressé, ou son représentant, doit avoir la possibilité de préparer l'audience, ce qui implique de traiter la demande d'examen du dossier en priorité et de mettre sans délai les pièces à disposition de l'avocat. Ce dernier doit à tout le moins pouvoir prendre connaissance en temps utile des bases légales sur lesquelles repose la décision. Dans le cadre de la procédure d'examen de la détention, il appartient aux juges, en dépit des contraintes de temps, de s'assurer que les droits des détenus soient garantis (arrêt 2C_598/2013 du 22 juillet 2013 consid. 3.2, destiné à la publication et références citées).
3.3. Le cas d'espèce se caractérise par la brièveté du délai imposé par l'art. 80 al. 1 LEtr selon lequel la légalité et l'adéquation de la détention doivent être examinées dans un délai de 96 heures par une autorité judiciaire. Saisi le 2 juillet 2013 d'une demande de prolongation de la détention administrative du recourant, le Tribunal administratif de première instance a désigné Me Arnaud Moutinot en qualité de défenseur d'office du recourant le 3 juillet 2013 et lui a fait parvenir le dossier. L'audience a été appointée au 4 juillet 2013, à 15.30 h. selon le recourant. Elle a été levée à 18 h. Il n'y a rien à redire quant au déroulement des préparatifs de cette audience, qui respecte le délai légal de l'art. 80 al. 1 LEtr.
Plus délicate est la question de savoir, au regard du droit d'être entendu, si l'avocat d'office du recourant a bénéficié de suffisamment de temps pour conférer avec son client avant l'audience. Le dossier ne contient pas d'explications sur les raisons de la limitation à dix minutes de la durée de l'entretien intervenu avant l'audience. Les inconvénients de la brièveté de l'entretien sont toutefois atténués par plusieurs facteurs. En premier lieu, la consultation du dossier remis à Me Arnaud Moutinot a permis à celui-ci de prendre connaissance de tous les éléments utiles de la situation personnelle de son client. En effet, ce dossier contenait notamment les sept jugements du Tribunal administratif de première instance rendus entre le 9 juillet 2012 et le 8 mai 2013 et les trois arrêts de la Cour de justice des 22 novembre 2012, 10 janvier 2013 et 24 janvier 2013. Toutes les circonstances de fait et tous les considérants de droit de la cause étaient donc connus de Me Arnaud Moutinot avant le début de l'audience du 4 juillet 2013. En second lieu, le recourant a été entendu lors de l'audience. Il a exposé les motifs pour lesquels il refusait de se rendre en Algérie, a fourni divers renseignements sur son état de santé et a fait état de son souhait d'être transféré au centre de Frambois, où il disposerait d'une chambre individuelle lui évitant de cohabiter avec un fumeur. Si Me Arnaud Moutinot l'avait estimé opportun, il aurait pu poser à son client les questions utiles à la défense de celui-ci, qu'il n'aurait, par hypothèse, pas eu le temps d'aborder avant l'audience. Enfin et surtout, il ressort du procès-verbal de l'audience que la Présidente du Tribunal administratif de première instance a indiqué à Me Arnaud Moutinot qu'il était toujours possible de solliciter des minutes de parloir supplémentaires en cas de nécessité. L'avocat pouvait donc demander à s'entretenir plus longtemps avec son client. On ignore si le conseil d'office du recourant a usé de cette faculté. L'avocat ne prétend en tout cas pas qu'on le lui aurait refusé. Ainsi, s'estimant suffisamment renseigné, il a plaidé la cause de son client en prenant des conclusions principales en libération immédiate et subsidiaires en transfert en foyer ouvert au centre de Frambois. Il a également requis certaines mesures d'instruction tendant à l'audition de deux médecins en qualité de témoins et à la mise en oeuvre d'une expertise médicale et psychiatrique. Il a donc pu faire valoir tous les éléments de fait et de droit utiles à la défense des intérêts de son client, en particulier les quelques faits nouveaux dont le Tribunal administratif de première instance n'avait pas encore connaissance. Compte tenu de l'ensemble des circonstances, il faut admettre que le recourant a pu bénéficier de la défense adéquate à laquelle il avait droit et que la durée de l'entretien avec son conseil avant l'audience certes brève ne constitue pas une violation de son droit d'être entendu, dès lors que le Tribunal a donné à l'avocat l'occasion de s'entretenir plus longtemps avec son client.
Au demeurant, il n'est pas contesté que la Cour de justice pouvait revoir librement la cause en fait et en droit. Or, selon la jurisprudence, pour autant qu'elle ne soit pas d'une gravité particulière, une violation du droit d'être entendu en instance inférieure est réparée lorsque l'intéressé a eu la faculté de se faire entendre en instance supérieure par une autorité disposant d'un plein pouvoir d'examen en fait et en droit (<ref-ruling> consid. 7.3 p. 562; <ref-ruling> consid. 3d/aa p. 437 s.; <ref-ruling> consid. 2b p. 131 s. et les arrêts cités). A supposer qu'elle ait été reconnue, la violation du droit d'être entendu du recourant devant le Tribunal administratif de première instance n'aurait pas revêtu un tel caractère de gravité - le recourant ne l'a, au demeurant, pas établi - et le vice aurait été réparé devant la Cour de justice.
Le grief du recourant lié à l'insuffisance du temps mis à sa disposition pour la préparation de sa défense doit en conséquence être écarté.
4.
Le recourant se plaint également d'une violation de l'art. 3 CEDH prohibant les traitements inhumains et dégradants dès lors qu'il a dû partager la chambre qu'il occupait à la maison de Favra avec un fumeur alors qu'il souffre d'asthme. Une telle exposition à la fumée pouvait ainsi constituer, de son point de vue, une condition de détention violant l'art. 3 CEDH.
Ce grief a été articulé par le recourant pour la première fois lors de son audition du 4 juillet 2013 auprès du Tribunal administratif de première instance. Le représentant de l'Office cantonal de la population a indiqué qu'il ignorait le problème de santé soulevé par le recourant et que le nécessaire serait fait afin d'y remédier. Comme le recourant a, conformément à sa demande, été transféré au centre de Frambois le 17 juillet 2013, il faut admettre que l'Office cantonal de la population a pris les mesures utiles pour donner satisfaction au recourant. S'agissant de la réaction des responsables de l'établissement de Favra, on ne saurait passer sous silence la détermination du 8 juillet 2013 de la directrice de l'établissement, qui a immédiatement réagi à la lecture du jugement du 4 juillet 2013 en soulignant que le recourant avait expressément et de façon menaçante demandé à partager sa cellule avec son colocataire fumeur, que le recourant était en outre lui-même fumeur, qu'il n'avait à aucun moment sollicité une place dans une cellule non-fumeur et que si tel avait le cas, il aurait immédiatement obtenu satisfaction. Ces propos, auxquels l'arrêt de la Cour de justice du 24 juillet 2013 se réfère pour envisager l'hypothèse d'un grief téméraire, n'ont pas été contredits par le recourant. Celui-ci est donc malvenu de se plaindre jusque devant le Tribunal fédéral d'une exposition à la fumée qu'il a non seulement consentie mais qu'il a même requise.
Le grief du recourant tiré de ses conditions de détention est donc manifestement mal fondé et à la limite de la témérité.
5.
Vu ce qui précède, le recours doit être rejeté.
Le recourant a sollicité l'assistance judiciaire. Or, au vu des circonstances particulières du cas d'espèce, le recours était dénué de chances de succès, voire parfois à la limite de la témérité, de sorte que la demande d'assistance judiciaire doit être rejetée (<ref-law>). S'agissant en particulier du grief relatif au droit d'être entendu, le Tribunal administratif de première instance a donné à l'avocat l'occasion de s'entretenir plus longtemps avec son client. L'avocat ne prétend du reste pas avoir été empêché d'user de cette faculté. Au demeurant, le grief aurait-il été fondé que le vice aurait de toute façon été réparé devant la Cour de justice (cf. supra consid. 3.3 in fine). Il se justifie en revanche de ne pas percevoir de frais de justice (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1.
Le recours est rejeté.
2.
La demande d'assistance judiciaire est rejetée.
3.
Il n'est pas perçu d'émolument judiciaire.
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, à la Cour de justice du canton de Genève, 1ère Section, et à l'Office fédéral des migrations.
Lausanne, le 15 octobre 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