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.

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_10/2009 du 5 février 2009 consid. 2 non publié aux <ref-ruling>).
1.2 Dans un seul acte, le recourant s'en prend à deux arrêts finaux (<ref-law>), émanant d'une autorité judiciaire cantonale supérieure de dernière instance (cf. art. 86 al. 1 let. d et al. 2 LTF). Le recours a été déposé à l'encontre de ces deux décisions le 14 janvier 2013, soit en temps utile compte tenu des féries (art. 46 al. 1 let. c et 100 LTF) et dans les formes requises (<ref-law>).
1.3 En principe, la qualité pour recourir auprès du Tribunal fédéral au sens de l'<ref-law> suppose un intérêt actuel et pratique à obtenir l'annulation de la décision attaquée. Si l'intérêt actuel disparaît en cours de procédure, le recours devient sans objet, alors qu'il est irrecevable si l'intérêt actuel faisait déjà défaut au moment du dépôt du recours (cf. <ref-ruling> consid. 1.3.1 p. 24).
En l'espèce, le premier arrêt du 28 novembre 2012 portait sur la détention du recourant jusqu'au 5 décembre 2012. Le second arrêt du 20 décembre 2012, en tant qu'il confirme la prolongation de cette détention jusqu'au 3 février 2013, s'est substitué à la première décision à partir du 6 décembre 2012. Il en découle que, lors du dépôt du recours, la détention administrative du recourant ne reposait que sur l'arrêt du 20 décembre 2012 qui déploie encore des effets au moment où la Cour de céans statue. Le recourant a donc qualité pour recourir à l'encontre de cette décision (cf. <ref-law>). En revanche, faute d'intérêt actuel, le recours interjeté le 14 janvier 2013 doit être déclaré irrecevable en tant qu'il s'en prend à l'arrêt du 28 novembre 2012. Il convient de préciser que, comme le recourant est toujours détenu sur la base de la seconde décision, la jurisprudence qui admet que le détenu libéré conserve un intérêt à faire constater le caractère illicite de sa détention (cf. <ref-ruling> consid. 4.3 p. 299 ss; <ref-ruling> consid. 1.3 p. 276 s.) n'est pas applicable.
Par conséquent, il y a lieu d'entrer en matière sur le recours dans la mesure où il concerne l'arrêt du 20 décembre 2012, étant rappelé que même dans le cadre d'une prolongation de la détention administrative, les motifs à l'origine de la détention peuvent être revus, indépendamment du fait qu'un recours ait ou non été valablement déposé contre la décision initiale (cf. arrêt 2C_1017/2012 du 30 octobre 2012 consid. 3 et les références citées).
1.4 La conclusion du recourant tendant à ordonner toutes mesures utiles à l'établissement des faits pertinents doit toutefois être déclarée irrecevable. En effet, le Tribunal fédéral n'ordonne des mesures probatoires (cf. <ref-law>) que de manière exceptionnelle (<ref-ruling> consid. 2 p. 104) et à condition que la partie qui les requiert motive sa requête (<ref-law>). Or, le mémoire de recours ne contient aucune motivation à l'appui de cette conclusion.
2. Le recourant invoque une violation des art. 78 al. 1 LEtr (RS 142.20) et 41 al. 2 PA (RS 172.021), ainsi que du principe de la proportionnalité. Il soutient en substance que les autorités sont obligées, de par la loi, de menacer préalablement la personne et de manière spécifique qu'elle risque une détention pour insoumission en lui laissant un délai suffisant pour qu'elle puisse s'exécuter, ce qui n'a pas été fait en l'espèce. En outre, la proportionnalité impliquait de le placer d'abord en détention en vue du renvoi au sens des art. 76 ss LEtr, avant de prononcer une détention pour insoumission, qui a un caractère subsidiaire et se présente comme une ultima ratio.
3. 3.1 La détention du recourant repose sur l'art. 78 al. 1 LEtr. Selon cette disposition, si l'étranger n'a pas obtempéré à l'injonction de quitter la Suisse dans le délai prescrit et que la décision exécutoire de renvoi ou d'expulsion ne peut être exécutée en raison de son comportement, il peut être placé en détention afin de garantir qu'il quittera effectivement le pays, pour autant que les conditions de la détention en vue du renvoi ou de l'expulsion ne soient pas remplies et qu'il n'existe pas d'autre mesure moins contraignante susceptible de conduire à l'objectif visé. Le but de la détention pour insoumission est de pousser un étranger tenu de quitter la Suisse à changer de comportement lorsque, à l'échéance du délai de départ, l'exécution de la décision de renvoi entrée en force ne peut être assurée sans la coopération de l'étranger malgré les efforts des autorités (cf. art. 78 LEtr; <ref-ruling> consid. 2.2.1 p. 107). La détention pour insoumission apparaît comme une ultima ratio, dans la mesure où il n'existe plus d'autres mesures permettant d'aboutir à ce que l'étranger présent illégalement en Suisse puisse être renvoyé dans son pays (arrêt 2C_639/2011 du 16 septembre 2011 consid. 3.1). Selon la jurisprudence, elle doit en tous les cas respecter le principe de la proportionnalité et suppose d'examiner l'ensemble des circonstances pour déterminer si elle paraît appropriée et nécessaire (cf. <ref-ruling> consid. 2.2.1 p. 107; <ref-ruling> consid. 2.3.2 p. 97).
3.2 En l'espèce et quoi qu'en dise le recourant, les conditions d'une détention pour insoumission sont clairement réunies. Il ressort des faits qui lient le Tribunal fédéral (cf. <ref-law>) que le recourant fait l'objet d'une décision de renvoi prononcée le 18 janvier 2010 en raison de son passé de délinquant, qui est définitive et exécutoire. Non seulement, il n'a pas obtempéré, mais il a encore continué à commettre des infractions sur le territoire suisse. A quatre reprises, les autorités lui ont réservé un vol de ligne et tenté de le renvoyer en Algérie, la dernière fois sous escorte policière. Le recourant a toujours refusé de monter dans l'avion en déclarant qu'il n'était pas d'accord de retourner dans son pays d'origine. En outre, il n'est pas possible d'envisager un retour en Algérie par vol spécial, celui-ci étant exclu par l'art. 4 al. 3 et 4 de l'Accord conclu le 3 juin 2006 et entré en vigueur le 26 novembre 2007 entre le Conseil fédéral de la Confédération suisse et le Gouvernement de la République algérienne démocratique et populaire sur la circulation des personnes (RS 0.142.111.279).
En pareilles circonstances, on ne voit pas quelle mesure moins incisive que la détention pour insoumission serait envisageable pour permettre de renvoyer le recourant. En effet, le refus réitéré de celui-ci de rentrer par vol ordinaire, doublé de l'impossibilité d'organiser un vol spécial vers l'Algérie, exclut la détention en vue du renvoi au sens de l'art. 76 LEtr (cf. arrêt 2C_624/2011 du 12 septembre 2011 consid. 2.3). En outre, par son attitude, le recourant démontre clairement qu'il n'a nulle intention de se conformer à la décision de renvoi dont il fait l'objet. Partant, bien qu'il s'agisse d'une ultima ratio, seule la détention au sens de l'art. 78 LEtr entre en ligne de compte.
3.3 Lorsque le recourant affirme qu'il n'aurait pas été suffisamment averti, en violation des <ref-law> et 78 LEtr, qu'il risquait une mise en détention pour insoumission, son grief confine à la témérité. En effet, selon les constatations cantonales, à chaque fois que le recourant s'est opposé physiquement à son renvoi avant le 5 novembre 2012, il lui a été rappelé qu'il s'exposait à des mesures de contrainte (cf. arrêt attaqué consid. 8 in fine p. 10). Depuis sa première tentative de renvoi, le 19 juin 2010, le recourant savait donc ce qu'il risquait, pourtant il n'a pas quitté la Suisse spontanément. Le recourant ayant été dûment averti, il est inutile de se demander si une mise en détention administrative serait aussi concevable sans avertissement et quels sont les liens entre l'<ref-law> et l'art. 78 LEtr. Quant au fait que l'autorité ait indiqué au recourant qu'il s'exposait à des mesures de contrainte, sans mentionner expressément la nature juridique de la mesure, à savoir la détention pour insoumission, il ne saurait s'agit d'un élément déterminant. Du reste, l'auteur cité par le recourant, selon l'opinion duquel un avertissement préalable serait toujours nécessaire, n'exige pas pour autant que celui-ci mentionne la détention pour insoumission (cf. TARKAN GÖKSU, in CARONI/GRÄCHTER/THURNHERR (ÉD.), Bundesgesetz über die Ausländerinnen und Ausländer, 2010, n° 10 in fine ad art. 78 AuG).
3.4 Au surplus, on ne voit pas que la détention pour insoumission, qui seule peut entrer en ligne de compte en l'espèce (cf. supra consid. 3.2 in fine), soit contraire à la proportionnalité, dès lors que le recourant se refuse clairement à se conformer à la décision de renvoi et n'a de cesse de commettre de nouvelles infractions en Suisse dès qu'il est remis en liberté. Arrivé à l'âge de 20 ans en Suisse, le recourant ne s'est du reste jamais intégré, comme en témoignent les nombreuses condamnations pénales qui ont justifié son renvoi. Il se prévaut d'un enfant né en 2006, mais non seulement il n'a noué aucune relation affective avec celui-ci, mais la réalité de sa paternité n'a pas été établie. Quant à l'existence d'une créance envers un ancien employeur, les juges cantonaux ont retenu à juste titre que ni la détention du recourant ni son renvoi en Algérie n'empêcherait de la faire valoir, par le biais de son représentant ou de sa mère. Partant, la détention pour insoumission, qui a pris effet à partir du 5 novembre 2012 et a été prolongée de deux mois (cf. art. 78 al. 2 LEtr), apparaît en l'état comme une mesure appropriée et nécessaire, qui reste encore dans le délai ordinaire prévu à l'art. 79 al. 1 LEtr.
Du reste, il suffirait au recourant de changer de comportement et d'accepter de monter dans un vol de retour pour l'Algérie, qui pourrait être organisé rapidement, puisqu'il est en possession d'un passeport algérien, pour mettre fin à la mesure de privation de liberté litigieuse.
4. Il résulte de ce qui précède que le recours doit être déclaré irrecevable en ce qu'il concerne l'arrêt du 28 novembre 2012 et rejeté dans la mesure de sa recevabilité en ce qu'il concerne l'arrêt du 20 décembre 2012.
Comme son recours paraissait d'emblée dénué de chances de succès, le recourant ne saurait bénéficier de l'assistance judiciaire (cf. <ref-law>). Au vu des circonstances de la cause, il se justifie toutefois de ne pas percevoir de frais pour la procédure fédérale (cf. <ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est irrecevable en ce qu'il concerne l'arrêt du 28 novembre 2012 et rejeté dans la mesure de sa recevabilité en ce qu'il concerne l'arrêt du 20 décembre 2012.
2. La demande d'assistance judiciaire est rejetée.
3. Il n'est pas perçu de frais judiciaires.
4. Le présent arrêt est communiqué aux mandataires du recourant, à l'Officier de police du canton de Genève, à 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 de la République et canton de Genève, Chambre administrative, 2ème section, et à l'Office fédéral des migrations.
Lausanne, le 29 janvier 2013
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: Zünd
La Greffière: Beti