Faits: A. De nationalité algérienne, né en 1984, X._ est arrivé à Genève en 2003. Sa mère résidant déjà dans le canton, il a été mis au bénéfice d'une autorisation de séjour dans le cadre d'un regroupement familial le 6 février 2004. A la suite de multiples condamnations pénales, l'Office de la population du canton de Genève (ci-après l'Office cantonal) a refusé par décision du 18 janvier 2010, de renouveler l'autorisation de séjour de X._ et a prononcé son renvoi de Suisse dès qu'il aurait satisfait aux autorités pénitentiaires. Cette décision est devenue définitive et exécutoire, le recours interjeté à son encontre par l'intéressé ayant été déclaré irrecevable le 2 juin 2010. A sa sortie de prison, le 19 juin 2010, X._ s'est opposé à son renvoi à destination d'Alger sur un vol de ligne qui avait été réservé pour lui le même jour. Le 26 novembre 2010, il a à nouveau été incarcéré à la suite de nouvelles infractions pénales. Le 24 mars 2011, le jour de sa sortie de prison, X._ s'est opposé à son renvoi à destination d'Alger par un vol de ligne réservé le jour-même à la demande de l'Office cantonal. Le 11 mai 2011, le 29 septembre 2011 et le 6 octobre 2011, X._ a commis plusieurs infractions pénales (vols, dommages à la propriété, violation de domicile; tentative de cambriolage). Le 4 février 2012, à sa sortie de prison, il aurait dû être refoulé à destination d'Alger, mais il s'est opposé à son renvoi par vol de ligne. Le 7 février 2012, X._ a été une nouvelle fois arrêté et condamné. A sa libération, le 5 novembre 2012, il a été remis entre les mains des services de police, en vue d'un vol avec escorte policière à destination d'Alger réservé le jour-même. Celui-ci n'a pu se concrétiser en raison de l'opposition de l'intéressé, qui a déclaré qu'il n'entendait pas retourner en Algérie, en faisant état d'un enfant dont il ignorait le nom et d'argent dû par son ex-employeur. B. B.a Le jour-même, soit le 5 novembre 2012, l'officier de police a ordonné la mise en détention administrative de X._ pour insoumission pour une durée d'un mois jusqu'au 5 décembre 2012, ce qu'a confirmé le Tribunal de première instance du canton de Genève (ci-après le Tribunal de première instance) par jugement du 8 novembre 2012. Le 27 novembre 2012, X._ a été entendu par la police et a déclaré: "je m'opposerai à mon renvoi jusqu'au bout" ou encore "je vais faire comme l'autre fois, je vais refuser de partir. Je m'opposerai de toutes les manières à mon renvoi, comme je vous l'ai déjà dit. Je ne rentrerai jamais en Algérie". Par arrêt du 28 novembre 2012, la Cour de justice du canton de Genève (ci-après la Cour de justice) a rejeté le recours formé par l'intéressé a l'encontre du jugement du 8 novembre 2012. B.b Statuant sur demande de l'Office cantonal et après avoir entendu X._, qui a réitéré son refus de retourner en Algérie, le Tribunal de première instance, par jugement du 3 décembre 2012, a prolongé la détention administrative jusqu'au 3 février 2013. Par arrêt du 20 décembre 2012, la Cour de justice a rejeté le recours de X._ à l'encontre de ce jugement. C. A l'encontre des arrêts du 28 novembre 2012 et du 20 décembre 2012, X._ forme un recours en matière de droit public au Tribunal fédéral. Il conclut, sous suite de frais et dépens, à l'annulation des arrêts attaqués et, principalement à sa libération immédiate, subsidiairement au renvoi de la cause à la Cour de justice pour qu'elle statue dans le sens des considérants. A titre encore plus subsidiaire, il demande à ce que toutes les mesures utiles à l'établissement des faits pertinents soient ordonnées. Il sollicite par ailleurs le bénéfice de l'assistance juridique complète, subsidiairement partielle. Les autorités ont été conviées à produire leur dossier sans échange d'écritures.