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.