Faits :
A.
Ressortissant algérien né en 1993, X._, alias Y._ (ci-après: l'intéressé), est entré en Suisse en 2011 et y a demandé l'asile.
Le 12 mars 2012, l'Office fédéral des migrations (devenu entretemps le Secrétariat d'Etat aux migrations; ci-après: le SEM) a refusé d'entrer en matière sur la demande d'asile et prononcé le renvoi de Suisse de l'intéressé. Le recours déposé par celui-ci contre cette décision auprès du Tribunal administratif fédéral a été rejeté le 4 mai 2012. L'intéressé a alors formé une demande de reconsidération du refus d'entrer en matière, qui a été rejetée tant par le SEM le 26 juillet 2012 que par le Tribunal administratif fédéral le 3 septembre 2012. Le 31 mai 2014, ce tribunal a aussi rejeté la demande de révision de son arrêt du 4 mai 2012 également déposée par l'intéressé.
Le canton de Genève a été chargé de l'exécution du renvoi. Le 25 mai 2012, l'office cantonal de la population et des migrations du canton de Genève (ci-après: l'office cantonal), a informé l'intéressé de son obligation de collaborer à son départ et des conséquences en cas de refus. Celui-ci a déclaré qu'il resterait en Suisse comme tout le monde.
Le 19 juin 2014, le SEM a informé l'office cantonal que l'intéressé avait été reconnu par les autorités algériennes et qu'un laissez-passer pouvait être obtenu auprès du consulat.
Le 28 juillet 2014, l'intéressé a indiqué à l'office cantonal qu'il n'avait pas commencé à organiser son retour en Algérie. Du 28 août 2014 au début du mois de janvier 2015, l'office cantonal a perdu sa trace.
Le 20 janvier 2015, l'office cantonal a demandé à la police genevoise d'exécuter le renvoi de l'intéressé. Le 22 janvier 2015, un billet d'avion a été réservé auprès d'Air Algérie au nom de l'intéressé pour un vol direct à destination d'Alger le 20 août 2015.
Une présentation auprès du Consul d'Algérie était prévue le 15 juillet 2015, mais l'intéressé n'a pu être trouvé ce jour-là.
Le 20 juillet 2015, l'officier de police a ordonné la mise en détention administrative de l'intéressé pour une durée de quatre mois. Le Tribunal de première instance du canton de Genève (ci-après: le TAPI) a entendu les parties le 23 juillet 2015. A cette occasion, l'intéressé a confirmé qu'il ne souhaitait pas retourner en Algérie et s'opposait à sa détention administrative. Il souffrait de migraines et avait un problème au bras gauche. Depuis qu'il était en Suisse, il logeait dans des foyers et était aidé par l'Hospice général. Il avait quitté le canton de Genève durant plusieurs mois en 2014 pour aller déposer une demande d'asile dans le canton de Bâle sans en aviser les autorités genevoises. S'il était libéré, il continuerait à se rendre à ses rendez-vous, mais ne monterait pas dans un avion pour rentrer en Algérie.
L'officier de police a indiqué qu'à la suite du rendez-vous manqué le 15 juillet 2015, il avait été demandé au Consul de voir le recourant avant le 20 août, mais celui-ci avait refusé, de sorte que le vol prévu ce jour-là avait dû être annulé; une demande en vue de réserver un nouveau vol avait été présentée au SEM. La mise en détention devait être confirmée au vu des démarches à entreprendre, l'intéressé pouvant y mettre fin en tout temps en décidant de partir volontairement.
Le 23 juillet 2015, le TAPI a confirmé l'ordre de mise en détention jusqu'au 20 novembre 2015. Le recours formé par l'intéressé a été rejeté par la Chambre administrative de la Cour de justice du canton de Genève (ci-après: la Cour de justice) le 12 août 2015.
Un nouveau vol a été réservé pour le 9 novembre 2015 puis annulé par swissREPAT en raison de l'embargo annoncé par Swiss concernant les renvois sur l'Algérie.
Les autorités ont entrepris de nouvelles démarches, car, sous réserve des retours volontaires pour lesquels il n'existait pas de restriction, seul Air Algérie acceptait les renvois et le délai d'attente pouvait se monter à six mois.
Le 26 octobre 2015, une place sur un vol à destination de l'Algérie a été obtenue et confirmée pour le 21 mars 2016, aucune date plus proche n'ayant pu être trouvée.
B.
A la demande de l'office cantonal, qui a confirmé que l'intéressé devait être présenté environ deux semaines avant la date du vol devant les autorités algériennes afin d'obtenir un laissez-passer, le TAPI a prolongé la détention administrative de l'intéressé, par jugement du 17 novembre 2015, pour une durée de cinq mois jusqu'au 20 avril 2016. Lors de l'audience de prolongation, l'intéressé a confirmé avoir utilisé un faux nom de famille et s'appeler X._.
Par arrêt du 8 décembre 2015, la Cour de justice a rejeté le recours formé par l'intéressé contre la prolongation de sa détention par le TAPI.
C.
Contre l'arrêt du 8 décembre 2015, l'intéressé interjette un recours en matière de droit public au Tribunal fédéral. A titre préalable, il demande le bénéfice de l'assistance judiciaire. Au fond, il conclut à l'annulation de l'arrêt du 8 décembre 2015 et à ce que sa mise en liberté soit ordonnée, subsidiairement au renvoi de la cause à l'autorité cantonale pour qu'elle statue dans le sens des considérants, sous suite de frais et dépens.
Ni l'office cantonal ni le TAPI n'ont formulé d'observations, pas plus que la Cour de justice, qui a déclaré persister dans les considérants et le dispositif de son arrêt. Le SEM a présenté des déterminations expliquant la situation des renvois à destination de l'Algérie et les démarches qui avaient été accomplies, en concluant à l'absence de violation du devoir de diligence lui incombant. Le recourant a formulé des observations finales, persistant dans les termes de son recours.

Considérant en droit :
1.
En matière de mesures de contraintes, les décisions tendant à la prolongation de la détention administrative émanant d'un tribunal supérieur statuant en dernière instance cantonale (art. 86 al. 1 let. d et al. 2 LTF) peuvent en principe faire l'objet d'un recours en matière de droit public auprès du Tribunal fédéral (arrêt 2C_751/2015 du 2 octobre 2015 consid. 1), dès lors qu'elles relèvent du droit public (<ref-law>) et ne tombent pas sous le coup d'une exception de l'<ref-law>. Partant, le présent recours, interjeté en temps utile, compte tenu des féries (art. 46 al. 1 let. c et <ref-law>) et dans les formes requises (<ref-law>), par le détenu qui a qualité pour recourir (<ref-law>), est recevable.
2.
Le Tribunal fédéral statue sur la base des faits établis par l'autorité précédente (cf. <ref-law>). Le recours ne peut critiquer les constatations de fait que si les faits ont été établis de façon manifestement inexacte ou en violation du droit au sens de l'<ref-law>, et si la correction du vice est susceptible d'influer sur le sort de la cause (<ref-law>), ce que la partie recourante doit démontrer d'une manière circonstanciée, conformément aux exigences de motivation de l'<ref-law> (cf. <ref-ruling> consid. 1.4.3 p. 254 s.). La notion de "manifestement inexacte" correspond à celle d'arbitraire au sens de l'art. 9 Cst. (<ref-ruling> consid. 2.1 p. 450).
Le recourant méconnaît ces principes. En effet, à l'appui de ses griefs, il présente sa propre version des faits et de son comportement, notamment lorsqu'il affirme avoir toujours été "collaborant et disponible" ou qu'il prétend que les autorités connaissaient son lieu de résidence lorsqu'il s'était absenté de Genève en 2014 pour déposer une nouvelle demande d'asile. Il en va de même dans ses observations finales, au sujet des raisons de son absence à l'audition du 15 juillet 2015 et du nombre d'entretiens nécessaires pour obtenir un laissez-passer des autorités algériennes. Dès lors qu'il ne se plaint ni a fortiori ne démontre l'arbitraire ou le caractère manifestement inexacte des faits, la Cour de céans n'a pas de motif de s'écarter des constatations de l'arrêt attaqué dans la suite de son raisonnement.
3.
La mise en détention administrative du recourant depuis le 20 juillet 2015, dont la prolongation jusqu'au 20 avril 2016 fait l'objet de la présente procédure, repose sur l'art. 76 al. 1 let. b ch. 3 et 4 LEtr. A juste titre, le recourant ne conteste pas tomber sous le coup de cette disposition (cf. à ce sujet <ref-ruling> consid. 5.3 p. 4). En effet, il a fait l'objet d'une décision de renvoi à laquelle il a n'a pas obtempéré; son comportement dénote en outre clairement un défaut de collaboration et une volonté d'entraver les démarches en vue d'exécuter son renvoi (refus réitérés de retourner en Algérie et d'entreprendre la moindre démarche en ce sens; utilisation d'un nom de famille erroné; absence de plusieurs mois sans aucun avis aux autorités genevoises).
4.
S'il ne conteste pas son titre de détention, le recourant invoque en premier lieu une violation des art. 76 al. 4 LEtr et 5 par. 4 CEDH, considérant que la prolongation de sa détention est disproportionnée et que les autorités n'ont pas agi avec célérité.
4.1. Selon l'art. 5 par. 4 CEDH, également applicable en matière de détention administrative (arrêt 2C_745/2010 du 31 mai 2011 consid. 3.3, non publié in <ref-ruling>), toute personne privée de sa liberté par arrestation ou détention a le droit d'introduire un recours devant un tribunal, afin qu'il statue à bref délai sur la légalité de sa détention et ordonne sa libération si la détention est illégale. Ce principe porte sur la durée mise par l'autorité judiciaire de première instance et, le cas échéant, par l'instance de recours cantonale, avant de statuer sur la mise en détention, respectivement sur une prolongation de celle-ci (cf. arrêt 2C_745/2010 du 31 mai 2011 consid. 3.3 et 3.4, non publiés in <ref-ruling>).
En l'espèce, on ne voit pas, et le recourant ne s'en plaint pas non plus, que les autorités judiciaires cantonales auraient tardé à statuer sur la prolongation de sa détention. Requise par l'office cantonal le 10 novembre 2015, la prolongation litigieuse a été prononcée par le TAPI le 17 novembre 2015, alors que la Cour de justice a rejeté le recours formé à son encontre le 27 novembre par l'intéressé le 8 décembre 2015. Ces délais ne révèlent aucune violation de l'art. 5 par. 4 CEDH. Le recourant semble au demeurant confondre les exigences découlant de l'art. 5 par. 4 CEDH, imposées aux autorités judiciaires, avec la célérité que l'on peut attendre des autorités administratives dans la préparation du renvoi, visée à l'art. 76 al. 4 LEtr.
4.2. Selon cette dernière disposition, les démarches nécessaires à l'exécution du renvoi ou de l'expulsion doivent être entreprises sans tarder. En outre, la durée de la détention doit être proportionnée par rapport aux circonstances d'espèce (arrêt 2C_218/2013 du 26 mars 2013 consid. 2.3). Selon la jurisprudence, le devoir de célérité est en principe violé lorsque, pendant plus de deux mois aucune démarche n'est plus accomplie en vue de l'exécution du renvoi par les autorités compétentes, sans que cette inaction soit en première ligne causée par le comportement des autorités étrangères ou celui du recourant lui-même (<ref-ruling> consid. 2.1 p. 211 et les arrêts cités).
Dans l'appréciation de la diligence des autorités, il faut notamment tenir compte de la complexité du cas, en particulier sous l'angle de l'exécutabilité du renvoi. Il faut en tous les cas se demander si la détention prononcée dans le cas d'espèce et sa durée demeurent nécessaires et restent dans une mesure proportionnée par rapport au but poursuivi (arrêt 2C_218/2013 du 26 mars 2013 consid. 2.3).
4.3. Il ressort des constatations cantonales que le recourant a été placé en détention le 20 juillet 2015, un vol à destination d'Alger étant réservé pour lui initialement le 20 août 2015. Comme il ne s'était pas présenté aux autorités algériennes lors du rendez-vous prévu le 15 juillet 2015 (les circonstances de l'absence du recourant, contestées par celui-ci, ne sont pas pertinentes pour juger de la diligence des autorités durant la détention) et que le Consul d'Algérie a refusé d'organiser une nouvelle audition d'ici au 20 août suivant, le SEM a annulé la réservation. Toujours au mois d'août, cette autorité a alors réservé un nouveau vol pour le 9 novembre 2015, qui a dû, lui aussi, être annulé en raison de l'embargo annoncé par la compagnie aérienne Swiss concernant les renvois sur l'Algérie. Dans la note d'annulation du SEM, il était indiqué que, compte tenu de cette situation et du fait que seul un renvoi avec Air Algérie était désormais possible, le délai d'attente pourrait se monter à six mois, bien que les renvois des personnes détenues soient traités en priorité. Il était précisé qu'il n'y avait en revanche aucune restriction concernant les retours volontaires en Algérie. Les autorités suisses ont organisé un nouveau départ et, le 26 octobre 2015, une place sur un vol à destination de l'Algérie a été obtenue pour le 21 mars 2016. Le recourant doit encore être présenté aux autorités algériennes en vue d'obtenir un laissez-passer, ce qui aura lieu environ deux semaines avant la date du vol, l'office cantonal en étant averti un ou deux mois auparavant, conformément à la pratique habituelle.
Il ressort de ces faits (qui lient la Cour de céans; <ref-law>) que le retard pris dans le renvoi du recourant et les périodes d'inaction des autorités suisses ne résultent pas d'un manque de diligence de leur part. En effet, peu après l'annulation du vol d'août 2015, celles-ci ont organisé un deuxième vol le 9 novembre 2015, qui a lui aussi dû être annulé en raison de l'embargo décrété par Swiss, soit pour des motifs indépendants de leur volonté. Les autorités ont alors obtenu, le 26 octobre 2015, un troisième vol à destination d'Alger pour le 21 mars 2016, aucune date plus proche n'ayant pu être trouvée. Ce délai d'attente, certes long, n'est donc pas davantage imputable aux autorités suisses; il résulte du fait que seul Air Algérie accepte d'assumer ces vols, mais aussi du comportement du recourant, puisqu'il a aussi été constaté que de telles restrictions n'existent pas pour les retours volontaires. Enfin, les autorités ne sont pas restées inactives, puisqu'il ressort de la réponse du SEM que celui-ci a tenté d'approcher la famille du recourant au mois de décembre 2015, afin d'inviter ses proches à le convaincre d'un retour volontaire en Algérie, mais la famille n'a pu être localisée à l'adresse indiquée. En pareilles circonstances, on ne discerne aucune violation de l'art. 76 al. 4 LEtr.
4.4. Les critiques du recourant reposent sur sa propre vision de la situation, qui ne tient pas compte des faits constatés, ce qui n'est pas admissible (cf. supra consid. 2). Tel est en particulier le cas lorsqu'il affirme qu'il ne va pas pouvoir obtenir de laissez-passer de la part des autorités algériennes. Elles confinent même à la témérité lorsque celui-ci ose affirmer qu'il s'est toujours montré collaborant et disponible.
4.5. Par ailleurs, bien que le délai d'attente jusqu'au prochain vol soit long, il n'apparaît pas que le maintien en détention jusqu'en avril 2016 soit contraire au principe de proportionnalité; en effet, la détention du recourant, depuis le mois de juillet 2015, apparaît encore d'une durée raisonnable, compte tenu de la situation particulière qui oblige de passer par Air Algérie à la suite de l'embargo de Swiss pour permettre le renvoi des ressortissants algériens.
5.
Dans un dernier grief, le recourant se prévaut de l'impossibilité d'exécuter son renvoi qui justifierait sa libération en application de l'art. 80 al. 6 let. a LEtr. Il se prévaut de l'embargo décrété par Swiss et du fait qu'un laissez-passer ne pourra pas être émis s'il est présenté aux autorités algériennes deux semaines avant le vol.
5.1. Selon l'art. 80 al. 6 let. a LEtr, s'il s'avère en particulier que l'exécution du renvoi ou de l'expulsion est impossible pour des raisons juridiques ou matérielles, la détention doit être levée. La jurisprudence a récemment rappelé que ces raisons doivent être importantes ("triftige Gründe") et qu'il ne suffit pas que l'exécution du renvoi soit momentanément impossible (par exemple faute de papiers d'identité), tout en restant envisageable dans un délai prévisible; l'exécution du renvoi doit être qualifiée d'impossible lorsque le rapatriement est pratiquement exclu, même si l'identité et la nationalité de l'étranger sont connues et que les papiers requis peuvent être obtenus (arrêts 2C_1072/2015 du 21 décembre 2015 consid. 3.2 et 2C_700/2015 du 8 décembre 2015 consid. 4.3.1).
5.2. Récemment, le Tribunal fédéral s'est prononcé sur l'application de l'art. 80 al. 6 let. a LEtr et a considéré que, réalisés par l'intermédiaire des vols Air Algérie, les renvois sous la contrainte ne pouvaient pas être qualifiés d'impossibles au sens de l'art. 80 al. 6 let. a LEtr (arrêt 2C_1072/2015 du 21 décembre 2015 consid. 3.3). La situation n'ayant pas évolué, la même conclusion peut être tirée en l'espèce.
5.3. Quant à l'impossibilité alléguée par le recourant d'obtenir un laissez-passer à temps, elle relève de pures conjectures. L'intéressé semble oublier qu'il n'est pas le premier Algérien que les autorités suisses renvoient par l'entremise d'Air Algérie et qu'il n'y a dès lors pas de raison de présumer que les démarches nécessaires à l'obtention d'un laissez-passer dans les délais lui permettant de prendre le vol prévu au 21 mars 2016 ne seront pas accomplies à temps.
Dans ces circonstances, le recours doit être rejeté.
6.
Le recours étant d'emblée dépourvu de chances de succès, il convient de rejeter la demande d'assistance judiciaire. Compte tenu de la situation du recourant, il sera néanmoins statué sans frais (art. 66 al. 1 in fine LTF). Il n'y a pas lieu d'allouer des dépens (art. 68 al. 1 et 3 LTF).

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 de frais de justice.
4.
Le présent arrêt est communiqué à la mandataire du recourant, à l'Officier de police du canton de Genève, au Tribunal administratif de première instance du canton de Genève, à l'Office cantonal de la population et des migrations du canton de Genève, à la Cour de justice de la République et canton de Genève, Chambre administrative, et au Secrétariat d'Etat aux migrations.
Lausanne, le 2 février 2016
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président : Zünd
Le Greffier : Ermotti