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.