Faits: A. Ressortissant de Guinée-Bissau né en 1994, X._ a déposé une demande d'asile en Suisse qui a été rejetée le 31 mars 2009 (recte : le 24 mai 2012, la date précédente étant celle du dépôt de ladite demande) par l'Office fédéral des migrations. Cette même décision prononçait le renvoi de Suisse du requérant dans un délai au 19 juillet 2012. Par arrêt du 6 août 2012, le Tribunal administratif fédéral a déclaré irrecevable le recours interjeté par X._ à l'encontre de la décision précitée. B. Par arrêt du 16 janvier 2013, le Juge unique de la Cour de droit public du Tribunal cantonal du canton du Valais (ci-après: le Juge unique), après avoir auditionné l'intéressé, a approuvé la décision du 12 janvier 2013 par laquelle le Service de la population et des migrations du canton du Valais (ci-après: le Service cantonal) a ordonné la mise en détention immédiate en vue du renvoi, pour trois mois au plus, de X._. C. A l'encontre de l'arrêt du 16 janvier 2013, X._ forme un recours en matière de droit public au Tribunal fédéral, en concluant à l'annulation de l'arrêt attaqué et à sa remise en liberté. Il demande par ailleurs qu'il soit constaté que sa détention du 12 janvier 2013 au jour de sa libération était illicite. Il sollicite en outre le bénéfice de l'assistance judiciaire et la nomination de Me Michel Dupuis, avocat à Monthey, en qualité d'avocat d'office. Le Service cantonal a transmis son dossier sans observations. Le Tribunal cantonal du canton du Valais a également renoncé à se déterminer. Invité à déposer d'éventuelles observations jusqu'au 22 février 2013, l'Office fédéral des migrations ne s'est pas déterminé. Par courrier du 26 février 2013 contenant diverses annexes, le conseil de X._ a indiqué au Tribunal fédéral que le Service cantonal lui avait envoyé, après le dépôt du recours en matière de droit public, une facture de 133 fr. pour frais de photocopies du dossier de son mandant. Il avait en vain demandé l'annulation de cette facture, car il n'avait pas sollicité la copie du dossier, mais seulement son envoi pour consultation en vue de préparer le recours au Tribunal fédéral. Le conseil de X._ a sollicité que le montant de 133 fr. lui soit remboursé à titre de débours dans le cadre du recours auprès de la Cour de céans. Invité à se déterminer au sujet de cette requête, le Service cantonal ne s'est pas prononcé dans le délai imparti.