Faits:
A. Le 27 (recte: 22) novembre 2012, X._, ressortissant irakien né en 1968, a été placé en détention administrative en vue de son renvoi par le Service de la population et des migrations du canton du Valais (ci-après: le Service cantonal) pour une durée de trois mois. Il ressort en substance de cette décision les éléments suivants:
X._ a déposé une demande d'asile en Suisse le 15 février 1999, qui a été rejetée le 18 décembre 2001. Il a été condamné pénalement en décembre 2003 et janvier 2004 à respectivement 20 mois et 2 ans d'emprisonnement et à l'expulsion du territoire suisse pour une durée de 10 ans pour lésions corporelles graves. Le 19 mai 2006, il a fait l'objet d'une détention administrative au motif qu'il n'avait accompli aucune démarche en vue de prouver son identité et de regagner son pays d'origine. Les démarches des autorités suisses ont révélé qu'il était également connu sous deux identités différentes, à savoir Y._ et Z._. Il a été libéré de sa détention administrative le 13 décembre 2006, après avoir été rendu attentif à son obligation de quitter la Suisse et de collaborer avec les autorités. En juin et octobre 2007, il a déclaré refuser de quitter la Suisse et n'a pas voulu s'informer sur les aides au départ dont il aurait pu bénéficier. Le 16 mars 2009, le Tribunal administratif fédéral a rejeté son recours contre le refus de l'Office fédéral des migrations (ci-après: l'Office fédéral) du 6 mars 2007 de réexaminer la décision de renvoi. Il a déposé une nouvelle demande de reconsidération le 21 janvier 2011, qui s'est soldée par un arrêt d'irrecevabilité du Tribunal administratif fédéral du 31 mai 2011. Depuis le 30 avril 2009, son lieu de domicile est inconnu des autorités suisses, tous les courriers le concernant étant adressés à son mandataire. Il a été placé en détention après avoir été reconduit en Valais par la police vaudoise. X._ a déclaré ne pas vouloir quitter la Suisse de manière autonome et n'avoir recherché aucun document prouvant son identité.
Cette mise en détention a été approuvée par le Juge unique de la Cour de droit public du Tribunal cantonal du canton du Valais (ci-après: le Juge unique) le 26 novembre 2012. Le 19 décembre 2012, X._ a recouru auprès du Tribunal fédéral et demandé sa libération immédiate. Son recours a été déclaré manifestement irrecevable par arrêt du 21 décembre 2012 (cause 2C_1260/2012).
Le 20 décembre 2011 (recte: 2012), X._ a refusé de monter dans un avion qui devait le ramener en Irak.
B. Le 11 février 2013, le Service cantonal a demandé au Juge unique de la Cour de droit public du Tribunal cantonal du canton du Valais (ci-après: le Juge unique) de prolonger la détention de X._ pour une durée de trois mois. X._ a conclu au rejet de cette demande, requérant également sa libération, subsidiairement à son assujettissement à une mesure de contrainte moins incisive.
Par arrêt du 21 février 2013 et à la suite d'une audience tenue le même jour, le Juge unique a admis la requête du Service cantonal. Il a prolongé la détention de X._ au 22 mai 2013 et rejeté la demande de libération de ce dernier.
C. A l'encontre de l'arrêt du 21 février 2013, X._ forme un recours en matière de droit public au Tribunal fédéral, au terme duquel il conclut à l'admission du recours, à l'annulation de l'arrêt du 21 février 2013 et à sa libération immédiate. Il demande par ailleurs l'octroi de l'assistance judiciaire.
La demande d'effet suspensif/mesures provisionnelles en vue d'empêcher l'exécution du renvoi formée parallèlement par X._ a été rejetée par ordonnance présidentielle du 2 avril 2013.
Le Tribunal cantonal a renoncé à se déterminer, à l'instar du Service cantonal et de l'Office fédéral. Par courrier du 19 avril 2013 adressé à la Cour de céans, X._ a persisté dans les considérants et conclusions de son recours.

Considérant en droit:
1. 1.1 En matière de mesures de contrainte, la décision rendue en dernière instance cantonale par le Juge unique valaisan peut faire l'objet d'un recours en matière de droit public au Tribunal fédéral (cf. arrêts 2C_237/2013 du 27 mars 2013 consid. 1.1; 2C_142/2013 du 1er mars 2013 consid. 1). Le recours a été interjeté en temps utile (<ref-law>) par le recourant dont la détention administrative a été prolongée à la suite de la procédure litigieuse et qui, partant, remplit les conditions de l'<ref-law>.
On peut toutefois se demander si le recours, tel qu'il est motivé, remplit les exigences de recevabilité prévues par la LTF. En effet, selon l'<ref-law>, les motifs doivent notamment exposer succinctement en quoi l'acte attaqué violé le droit. Le mémoire doit donc s'en tenir à l'essentiel et ne pas être inutilement long (arrêt 4A_709/2011 du 31 mai 2012 consid. 1.2). En l'occurrence, l'avocat du recourant a déposé un recours de 36 pages au Tribunal fédéral, alors que la problématique juridique ne pose pas de difficultés particulières et que l'arrêt attaqué ne fait que trois pages. Une telle écriture est prolixe. Elle aurait pu être renvoyée à son auteur pour qu'il remédie à l'irrégularité (cf. <ref-law>; arrêt 2C_715/2011 du 2 mai 2012 consid. 1.4). Compte tenu de l'issue du litige, la Cour de céans a cependant choisi d'entrer en matière.
1.2 Saisi d'un recours en matière de droit public, le Tribunal fédéral se fonde sur les faits constatés par l'autorité précédente (cf. <ref-law>), à moins que ces faits n'aient été établis de façon manifestement inexacte - ce qui correspond à la notion d'arbitraire (cf. <ref-ruling> consid. 7.1 p. 51; <ref-ruling> consid. 2.4 p. 313 s.) - ou en violation du droit au sens de l'<ref-law> (cf. <ref-law>). La partie recourante qui entend s'écarter des constatations de l'autorité précédente doit expliquer de manière circonstanciée en quoi les conditions d'une exception prévue par l'<ref-law> seraient réalisées; à défaut, il n'est pas possible de tenir compte d'un état de fait qui diverge de celui contenu dans la décision attaquée. En particulier, le Tribunal fédéral n'entre pas en matière sur des critiques de type appellatoire portant sur l'état de fait ou sur l'appréciation des preuves (<ref-ruling> consid. 5.1 p. 356; <ref-ruling> consid. 3 p. 104). Il ne suffit donc pas, comme le fait le recourant tout au long de son mémoire, de présenter librement sa propre version des événements pour en déduire que la décision attaquée viole le droit. Il ne sera pas tenu compte d'une telle argumentation. Seules les critiques relatives aux faits répondant aux exigences de motivation précitées seront examinées.
2. Bien que le recourant les invoque en fin de mémoire, il convient de traiter d'emblée des griefs d'ordre formel (<ref-ruling> consid. 5.1 p. 390; arrêt 2C_84/2012 du 15 décembre 2012 consid. 2).
2.1 Le recourant se plaint de ce que la décision attaquée souffre d'un défaut de motivation contraire à l'art. 29 Cst.
La jurisprudence a déduit de l'art. 29 al. 2 Cst. le devoir pour le juge de motiver sa décision, afin que le destinataire puisse en saisir la portée, le cas échéant, l'attaquer en connaissance de cause et que l'autorité de recours puisse exercer son contrôle (<ref-ruling> consid. 3.3 p. 445 s. et les arrêts cités). Pour répondre à ces exigences, il suffit que le juge mentionne, au moins brièvement, les motifs qui l'ont guidé et sur lesquels il a fondé sa décision (<ref-ruling> consid. 3.2 p. 270; <ref-ruling> consid. 5.2 p. 236).
L'arrêt attaqué est certes sommairement motivé, mais suffisamment pour que l'on comprenne le raisonnement suivi. Ainsi, contrairement à ce que soutient le recourant, le Juge unique, après avoir constaté l'existence d'un risque que le recourant se soustraie à son renvoi, pouvait se limiter à considérer que les mesures moins rigoureuses que la détention ne seraient pas en mesure de préserver l'intérêt public poursuivi, sans avoir encore à examiner dans le détail les différentes mesures proposées. En outre, constater que les autorités ont agi avec la célérité nécessaire, permet de comprendre pourquoi aucune violation de l'art. 76 al. 4 LEtr n'a été retenue, ce qui suffit sous l'angle de 29 al. 2 Cst. Il en va de même lorsque le Juge unique a indiqué que les critiques du recourant portant sur la légalité de son renvoi n'étaient pas pertinentes. Le recourant a du reste saisi le raisonnement et attaqué ce point dans son écriture (cf. infra consid. 4). Le grief est donc infondé.
2.2 Sous l'angle formel, le recourant reproche également aux autorités de n'avoir pas respecté le délai de l'art. 80 al. 2 LEtr, dès lors que l'audience devant le Tribunal cantonal n'a eu lieu que dix jours après la demande de prolongation présentée par le Service cantonal, alors que la prolongation de la détention doit être examinée dans un délai de huit jours.
Dès lors que l'art. 80 al. 2 LEtr concerne la mise en détention et impose à l'autorité judiciaire de statuer dans un délai de 96 heures, on ne voit pas en quoi cette disposition aurait pu être violée en relation avec la prolongation de la détention ici litigieuse. Le délai de huit jours dont se prévaut le recourant est prévu à l'art. 80 al. 5 LEtr en relation avec une demande de levée de détention. Le recourant n'indique pas clairement avoir formé une telle demande et surtout ne donne pas la date à laquelle il l'aurait le cas échéant présentée. Partant, on ne voit pas quel délai aurait violé l'arrêt attaqué rendu le 21 février 2013.
3. Invoquant l'arbitraire (art. 9 Cst.), le recourant s'en prend aux faits retenus. Ses critiques sont manifestement infondées, si tant est que la motivation présentée puisse être considérée comme recevable (cf. <ref-law>).
3.1 Contrairement à ce que le recourant soutient, le fait que la date d'un vol spécial à destination de l'Irak ne soit pas encore fixée n'a pas pour effet que sa détention serait prononcée pour une durée indéterminée. La décision attaquée la limite du reste expressément au 22 mai 2013. Au demeurant, le courriel de l'Office fédéral du 21 février 2013 sur lequel se fonde le recourant pour affirmer qu'aucune démarche ne serait entreprise en vue d'organiser un vol spécial à destination de l'Irak a été cité de manière tronquée. Compte tenu du passé pénal du recourant, l'Office fédéral y informait en effet les autorités valaisannes de ce qu'il soumettrait le cas du recourant aux autorités nord-irakiennes pour qu'elles consentent au renvoi forcé de l'intéressé vers leur territoire (<ref-law>).
3.2 Lorsque le recourant reproche au Juge unique de ne pas avoir retenu les indices concrets démontrant qu'il entendait collaborer avec les autorités et quitter la Suisse, le grief confine à la témérité. En effet, il ressort de la procédure de mise en détention du 22 novembre 2012 que le recourant a fait l'objet d'une décision de renvoi en décembre 2001 déjà, qu'il a été expulsé pénalement pour une durée de 10 ans en 2003, qu'il a été placé durant neuf mois en détention administrative en 2006 dès lors qu'il n'entendait pas se soumettre à son obligation de quitter la Suisse, qu'entendu en 2007, il a refusé de quitter la Suisse, que depuis avril 2009, les autorités ne connaissaient plus son domicile et enfin, qu'il a répété, au moment de sa nouvelle mise en détention administrative, ne pas être disposé à quitter la Suisse de manière autonome.
3.3 Enfin, on ne voit pas que ce serait de manière insoutenable que le Juge unique n'aurait pas tenu compte des déclarations du recourant faites dans la procédure de renvoi liées au risque encouru en cas de retour en Irak, dès lors que ces éléments ne sont pas pertinents dans la présente procédure (cf. infra consid. 6).
4. Le recourant conteste l'existence d'un motif de détention.
4.1 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 (arrêts 2C_26/2013 du 29 janvier 2013 consid. 1.3; 2C_1017/2012 du 30 octobre 2012 consid. 3 et les références citées). Il convient donc d'examiner ce point, peu importe que la Cour de céans ait déclaré irrecevable, le 21 décembre 2012 (cf. arrêt 2C_1260/2012 précité), le recours interjeté par le recourant à l'encontre de sa mise en détention.
4.2 La détention du recourant repose sur l'art. 76 al. 1 let. b ch. 3 LEtr, selon lequel, si des éléments concrets font craindre que la personne concernée entende se soustraire au renvoi ou à l'expulsion, en particulier parce qu'elle ne se soumet pas à son obligation de collaborer en vertu de l'art. 90 de la présente loi (...). Eu égard au comportement du recourant tel que décrit précédemment (cf. supra consid. 3.2), en particulier la volonté affichée de rester en Suisse depuis 2001, malgré une première détention administrative en 2006, sa réticence à accomplir les démarches propres à obtenir des documents d'identité et son refus de prendre le vol prévu à son intention le 20 décembre 2012, on ne voit manifestement pas que sa détention ne soit pas justifiée sous l'angle de l'art. 76 al. 1 let. b ch. 3 LEtr.
4.3 La détention reposant sur un motif prévu dans la LEtr, il n'y a pas lieu d'examiner si, au surplus, l'art. 76 al. 1 let. b ch. 5 LEtr, également mentionné dans l'arrêt attaqué sans autre développement, serait applicable. Au demeurant, le chiffre 5 de l'art. 76 al. 1 let. b LEtr, a visiblement été mentionné par inadvertance à la place du chiffre 4, dès lors qu'il ne vise à l'évidence pas la situation du recourant.
5. Selon le recourant, les autorités tardent à effectuer les démarches nécessaires à son renvoi, violant ainsi l'art. 76 al. 4 LEtr.
5.1 Selon la jurisprudence, on considère en règle générale que les autorités n'agissent pas avec la diligence nécessaire lorsque, durant plus de deux mois, aucune démarche en vue du renvoi n'est entreprise, sans que ce retard ne soit en premier lieu imputable au comportement des autorités ou à l'intéressé lui-même (arrêt 2C_804/2008 du 5 décembre 2008 consid. 4.2; <ref-ruling> consid. 3a p. 51).
5.2 Il ressort de la procédure de détention que les autorités du Nord-Irak ont donné leur accord quant au retour de l'intéressé sur leur territoire. Un vol a en effet été organisé après la mise en détention du recourant en novembre 2012. Toutefois, le 20 décembre 2012, l'intéressé a refusé de monter dans l'avion qui devait le ramener en Irak, de sorte que seul un vol spécial était désormais envisageable. Dans sa demande de prolongation de détention du 11 février 2013, le Service cantonal a indiqué qu'un tel vol était en préparation avec la collaboration des autorités fédérales. Selon un échange de courriels produits par le recourant - qui peut être pris en compte en regard de l'<ref-law>, dès lors qu'il s'agit d'éléments pertinents pour apprécier le bien-fondé du maintien de l'étranger en détention (arrêts 2C_256/2013 du 10 avril 2013 consid. 2; 2C_142/2013 du 1er mars 2013 consid. 3) -, l'Office fédéral a indiqué, le 21 février 2013, que pour l'instant aucun vol spécial n'était prévu pour le Nord de l'Irak.
Il ressort de ces éléments que certes, le renvoi du recourant a pris du retard et qu'il n'était pas envisageable immédiatement. Cependant, ce retard, de même que la prolongation de la détention administrative, sont en grande partie imputables au recourant, étant donné qu'il a refusé de monter dans le vol prévu le 20 décembre 2012. Il n'y a donc pas, en l'état, violation de l'art 76 al. 4 LEtr. Il appartient cependant aux autorités de poursuivre, avec diligence, les démarches, afin de pouvoir concrétiser le renvoi du recourant dès que possible.
6. Le recourant affirme également que le renvoi serait impossible, ce qui justifierait sa libération en vertu de l'art. 80 al. 6 LEtr, dès lors qu'un retour dans son pays le mettrait concrètement en danger. Il se prévaut également des art. 7 du Pacte ONU II (RS 0.103.2), 3 CEDH (RS 0.101) et 3 CCT (0.105), qui interdisent toute forme de torture. Ce faisant, le recourant remet en cause les conséquences de son renvoi.
6.1 Comme la Cour de céans l'avait déjà indiqué au recourant dans son arrêt du 21 décembre 2012, la procédure liée à la détention administrative ne permet pas, sauf cas exceptionnels, de remettre en cause le caractère licite de la décision de renvoi (arrêt 2C_1260/2012 consid. 3.2; <ref-ruling> consid. 4.3.2 p. 149). Ce n'est que si une décision de renvoi apparaît manifestement inadmissible, soit arbitraire ou nulle, qu'il est justifié de lever la détention en application de l'art. 80 al. 6 let. a LEtr, étant donné que l'exécution d'un tel ordre illicite ne doit pas être assurée par les mesures de contrainte (arrêt 2C_256/2013 du 10 avril 2013 consid. 4.5 et les arrêts cités).
6.2 En l'espèce, le recourant a fait l'objet d'une décision de renvoi en 2001. Il a formé en vain deux demandes de réexamen/reconsidération, les autorités considérant que son renvoi vers le Kurdistan irakien demeurait possible et ne l'exposerait pas à un risque concret pour sa vie ou son intégrité corporelle ou psychique. Devant la Cour de céans, le recourant présente, sous le couvert de l'art. 80 al. 6 let. a LEtr une argumentation appellatoire dont il ne peut être tenu compte (cf. supra consid. 1.2). Au demeurant, il ne démontre ni du reste n'allègue que la décision de renvoi et le refus de réexaminer celle-ci seraient manifestement inadmissibles ou reviendraient à violer ses droits fondamentaux (<ref-law>; cf., s'agissant du principe du non-refoulement, arrêt 2C_935/2011 du 7 décembre 20121 consid. 7.1). Le grief est donc infondé, dans la mesure où il est recevable.
7. Par ailleurs, en tant que le recourant affirme être disposé à quitter la Suisse, de son propre gré, pour se rendre dans un pays sûr autre que l'Irak, il ne peut rien tirer de cet argument par rapport au maintien de la détention administrative. Le renvoi dans un pays tiers du choix de l'étranger présuppose en effet que ce dernier ait la possibilité de s'y rendre légalement et constitue, qui plus est, une faculté ("peut") de l'autorité compétente (cf. art. 69 al. 2 LEtr; voir également arrêt 2C_393/2009 du 6 juillet 2009 consid. 3.4). Or, le recourant étant sans papiers et n'alléguant pas disposer de documents qui lui permettraient de se rendre dans un autre Etat que l'Irak, les conditions propres à l'art. 69 al. 2 LEtr ne sont pas réunies.
8. En outre, le recourant soutient que d'autres mesures permettraient d'assurer son renvoi de Suisse, en particulier l'assignation à résidence (art. 74 al. 1 let. b LEtr) ou le port d'un bracelet électronique, que le Juge unique devait envisager concrètement.
Il ressort de la procédure que le recourant a été placé en détention administrative après avoir été ramené en Valais par la police vaudoise, alors que, depuis avril 2009, il avait disparu du foyer de A._ où il résidait et qu'à partir de ce moment, son lieu de domicile était inconnu des autorités. En pareilles circonstances, celui-ci est particulièrement malvenu de reprocher au Juge unique une violation du droit fédéral, parce qu'il a estimé, sans plus ample examen, qu'une assignation à résidence ou d'autres mesures moins incisives ne permettraient pas de garantir l'exécution de son renvoi.
9. Enfin, la prolongation jusqu'au 22 mai 2013 apparaît encore proportionnée, dès lors que le recourant a été placé en détention le 22 novembre 2012 et qu'il a lui-même refusé d'y mettre fin en prenant un vol qui était organisé en vue de son retour en décembre 2012, imposant aux autorités d'entreprendre de nouvelles démarches en vue d'un renvoi forcé et de prolonger sa détention afin d'en assurer la bonne exécution.
10. Il résulte de ce qui précède que le recours doit être rejeté dans la mesure de sa recevabilité.
Comme le recours paraissait d'emblée dénué de chances de succès, le recourant ne saurait bénéficier de l'assistance judiciaire (cf. art. 64 al. 1 et 2 LTF). 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>). Il ne sera pas alloué de dépens (art. 68 al. 1 et 3 LTF).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté dans la mesure où il est recevable.
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é au mandataire du recourant, au Service de la population et des migrations du canton du Valais, au Juge unique de la Cour de droit public du Tribunal cantonal du canton du Valais, ainsi qu'à l'Office fédéral des migrations.
Lausanne, le 23 avril 2013
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: Zünd
Le Greffier: Chatton