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.