Faits:
A. Né en 1972, X._ se prétend ressortissant du Turkménistan.
Par décision du 26 juin 2009, l'Office fédéral des migrations (ci-après: l'Office fédéral) n'est pas entré en matière sur sa demande d'asile et a ordonné son renvoi de Suisse. Le recours interjeté par X._ à l'encontre de cette décision a été déclaré irrecevable par arrêt du Tribunal administratif fédéral du 14 octobre 2009.
Le 12 juin 2012, le Service de la population et des migrations du canton du Valais a placé X._ en détention administrative. Le 3 septembre 2012, il a requis la prolongation de cette détention auprès du Tribunal cantonal valaisan.
Lors de l'audience qui s'est tenue le 10 septembre 2012 devant le Juge unique du Tribunal cantonal (ci-après: le Juge unique), le Service cantonal a expliqué que les autorités du Turkménistan n'avaient pas encore répondu à la lettre de l'Office fédéral du 14 juin 2012 sollicitant un laissez-passer pour X._. Celui-ci a pour sa part demandé à être libéré, alléguant avoir souvent affirmé être d'accord de s'en aller, et a prétendu qu'aucun élément du dossier ne dénotait chez lui un risque de passage dans la clandestinité.
Par arrêt du 10 septembre 2012, le Juge unique, donnant suite à la requête du Service cantonal, a prolongé la détention de X._ jusqu'au 13 décembre 2012 et rejeté sa demande de libération.
B. Contre l'arrêt du 10 septembre 2012, X._ dépose un recours en matière de droit public auprès du Tribunal fédéral, en concluant à l'admission du recours et à sa libération. Subsidiairement, il demande le renvoi à l'instance inférieure pour nouvelle décision dans le sens des considérants et, plus subsidiairement encore, à ce qu'il soit astreint à s'annoncer ou à ce qu'un bracelet électronique lui soit posé. Il requiert par ailleurs le bénéfice de l'assistance judiciaire.
Le Tribunal cantonal a renoncé à se déterminer. Le Service cantonal a transmis son dossier, sans observations. L'Office fédéral n'a pas pris position. Le 24 octobre 2012, le Service cantonal a informé le Tribunal fédéral du fait que l'Ambassade du Turkménistan avait refusé d'octroyer un laissez-passer en faveur de X._, au motif qu'il était inconnu dans cet Etat et qu'aucun document ne pouvait établir qu'il en possédait la nationalité. Seule une demande de réadmission en Russie était donc envisageable et l'Office fédéral avait entrepris des démarches auprès des autorités russes en vue de la réadmission du recourant.
Considérant en droit:
1. En matière de mesures de contrainte, la décision rendue en dernière instance cantonale par le Juge unique peut faire l'objet d'un recours en matière de droit public au Tribunal fédéral (cf., notamment, arrêts 2C_413/2012 du 22 mai 2012 consid. 1; 2D_66/2011 du 13 décembre 2011 consid. 1). Interjeté en temps utile (art. 100 al. 1 LTF) et dans les formes requises (art. 42 LTF) par le recourant qui se trouve en détention administrative et remplit partant les conditions de l'art. 89 al. 1 LTF, le présent recours est en principe recevable.
2. L'examen du Tribunal fédéral se fonde sur les faits constatés par l'autorité précédente (cf. art. 105 al. 1 LTF), à moins que ces faits n'aient été établis de façon manifestement inexacte - notion qui correspond à celle d'arbitraire (ATF 137 I 58 consid. 4.1.2 p. 62; cf. ATF 136 III 552 consid. 4.2 p. 560) - ou en violation du droit au sens de l'art. 95 LTF (cf. art. 105 al. 2 LTF). Aucun fait nouveau ni preuve nouvelle ne peut être présenté à moins de résulter de la décision de l'autorité précédente (art. 99 al. 1 LTF).
Il en découle qu'il ne sera pas tenu compte des faits contenus dans le recours qui s'écartent des constatations cantonales, à moins que les conditions de l'art. 105 al. 2 LTF ne soient réalisées. En revanche, étant donné que, lors de la prolongation d'une détention administrative, les autorités doivent aussi en vérifier les motifs (cf. consid. 3 infra), le Tribunal fédéral peut, en tant que de besoin, tenir compte des éléments de fait ressortant de l'arrêt du Juge unique qui confirment la mise en détention initiale. Enfin, les éléments nouveaux de nature à confirmer ou infirmer l'imminence de l'exécution du renvoi qui sont transmis au Tribunal fédéral par les autorités peuvent être pris en compte en application de l'art. 99 al. 1 LTF, dans la seule mesure où ils sont pertinents pour apprécier le bien-fondé du maintien de l'étranger en détention.
3. Le recourant a été placé en détention administrative en vue du renvoi le 12 juin 2012 pour une durée de trois mois, ce qu'a confirmé le Juge unique le 15 juin suivant. Il n'a alors pas recouru. La présente procédure concerne la prolongation de la détention pour une durée de trois mois, accordée par le Juge unique à la demande du Service cantonal.
La détention administrative porte une atteinte grave à la liberté personnelle et ne peut être ordonnée que dans le respect de l'art. 5 CEDH (arrêt 2C_413/2012 du 22 mai 2012 consid. 3.1; cf. ATF 135 II 105 consid. 2.2.1 p. 107) et de l'art. 31 Cst., ce qui suppose en premier lieu qu'elle repose sur une base légale (art. 36 al. 1 Cst.; arrêts 2C_584/2012 du 29 juin 2012 consid. 5.1; 2C_478/2012 du 14 juin 2012 consid. 2.1). Partant, l'existence d'un motif légal justifiant la détention doit être vérifiée par le juge à tous les stades de la procédure, soit également lors d'une demande de mise en liberté ou de prolongation de la détention, peu importe que l'étranger détenu n'ait pas recouru contre sa mise en détention initiale. Lors de cet examen, l'autorité doit prendre en compte les circonstances retenues dans la décision de mise en détention (arrêt 2C_952/2011 du 19 décembre 2011 consid. 3.2; cf. ATF 122 I 275 consid. 3b p. 277; voir aussi sur ce point: THOMAS HUGI YAR, Zwangsmassnahmen im Ausländerrecht, in: Ausländerrecht [Peter Uebersax et al. (éds)], 2e éd., Bâle 2009, n. 10.33 p. 417 ss, 439).
Avant de se prononcer sur l'admissibilité de la prolongation de la détention du recourant, il convient donc de s'interroger sur le bien-fondé de la détention elle-même, que conteste du reste le recourant.
4. La mise en détention du recourant prononcée le 12 juin 2012, qui a été approuvée par le Juge unique le 15 juin 2012, reposait sur l'art. 76 al. 1 let. b ch. 3 et 5 LEtr.
4. La mise en détention du recourant prononcée le 12 juin 2012, qui a été approuvée par le Juge unique le 15 juin 2012, reposait sur l'art. 76 al. 1 let. b ch. 3 et 5 LEtr.
4.1 4.1.1 Selon la jurisprudence, les motifs de l'art. 76 al. 1 let. b ch. 3 LEtr (en relation avec l'al. 4 de cette disposition) sont réalisés en particulier lorsque l'étranger tente d'entraver les démarches en vue de l'exécution du renvoi en donnant des indications manifestement inexactes ou contradictoires ou encore s'il laisse clairement apparaître, par ses déclarations ou son comportement, qu'il n'est pas disposé à retourner dans son pays d'origine (cf. ATF 130 II 56 consid. 3.1 p. 58 s.; arrêts 2C_413/2012 du 22 mai 2012 consid. 3.2; 2C_963/2010 du 11 janvier 2011 consid. 2.1). Comme le prévoit expressément l'art. 76 al. 1 let. b ch. 3 LEtr, il faut qu'il existe des éléments concrets en ce sens (arrêts 2C_505/2012 du 19 juin 2012 consid. 4.1; 2C_478/2012 du 14 juin 2012 consid. 2.2; 2C_413/2012 du 22 mai 2012 consid. 3.2 in fine; 2C_675/2011 du 20 septembre 2011 consid. 2.1).
Ne constituent pas des éléments suffisants le seul fait que l'étranger est entré en Suisse de façon illégale ou le fait qu'il soit démuni de papiers d'identité (cf. ATF 129 I 139 consid. 4.2.1 p. 146 s.). De même, le fait de ne pas quitter le pays dans le délai imparti à cet effet n'est pas à lui seul suffisant pour admettre un motif de détention au sens de l'art. 76 al. 1 let. b ch. 3 (voire ch. 4) LEtr, mais peut tout au plus constituer un indice parmi d'autres en vue d'établir un risque de fuite (cf. arrêts 2C_478/2012 du 14 juin 2012 consid. 2.2; 2A.208/1998 du 29 avril 1998 consid. 3; 2A.514/1997 du 9 décembre 1997 consid. 1b; ALAIN WURZBURGER, La jurisprudence récente du Tribunal fédéral en matière de police des étrangers, in: RDAF 1997 I 267 ss, p. 332 s.; HUGI YAR, op. cit., n. 10.84 p. 417 ss, 463). En effet, si tel était le cas, il aurait appartenu au législateur d'indiquer expressément à l'art. 76 al. 1 LEtr que le non-respect du délai de départ constitue à lui seul un motif justifiant la mise en détention de l'étranger. A l'inverse, la circonstance que la personne concernée s'est tenue, assez longtemps et de manière ininterrompue, en un endroit stable à la disposition des autorités plaide en défaveur du risque de fuite (arrêt 2C_478/2012 du 14 juin 2012 consid. 2.2 et les références citées).
4.1.2 En l'espèce, l'arrêt attaqué ne contient pas d'élément tangible suffisant, propre à justifier la détention du recourant sur la base de l'art. 76 al. 1 let. b ch. 3 LEtr.
Le seul élément concret retenu réside dans le fait que le recourant n'a donné aucun détail vérifiable sur son identité et n'avait toujours pas de papiers, bien qu'il ait, en 2009, offert de se procurer assez rapidement des documents officiels si le délai qui lui avait été fixé pour quitter la Suisse à l'époque était prolongé jusqu'à la fin de l'année en cours. Il s'agit là certes d'un indice susceptible, selon les circonstances, de justifier la mise en détention de l'étranger, étant donné qu'il incombe à ce dernier, d'après l'art. 90 let. c LEtr, de se procurer une pièce de légitimation ou de collaborer avec les autorités pour en obtenir une, partant de déployer activement des efforts aux fins d'organiser son retour. En l'espèce, la pertinence de cet indice doit cependant être relativisée. En effet, le comportement reproché au recourant remonte à l'année 2009 et s'inscrit dans le cadre de la procédure d'asile. Or, depuis son retour en Suisse en mars 2011, les autorités suisses n'ont, à teneur du dossier, pris aucune mesure ni même indiqué au recourant qu'il lui appartient d'organiser son départ de Suisse et de se procurer les papiers nécessaires avant de le placer en détention administrative. Il résulte de ce qui précède qu'en l'occurrence, le comportement du recourant en 2009 n'est, à lui seul, pas suffisant pour justifier le maintien en détention de celui-ci en 2012.
Pour le surplus, ni la décision de mise en détention du 12 juin, pas plus que sa confirmation par le Juge unique le 15 juin 2012 ne contiennent d'autres éléments concrets propres à établir que le recourant se refuserait à obtempérer aux injonctions des autorités ou entendrait se soustraire au renvoi. On ne peut en particulier lui reprocher d'avoir disparu à fin 2009, puisqu'il a quitté la Suisse donnant ainsi suite à la décision refusant d'entrer en matière sur sa demande d'asile et ordonnant son renvoi. Il a toutefois été reconduit en Suisse le 24 mars 2011 par les autorités allemandes auprès desquelles il avait entre-temps déposé une autre requête d'asile. Certes, à partir de ce moment, le recourant est resté en Suisse sans aucun titre de séjour. Cependant, rien n'indique que les autorités lui aient, depuis lors, fixé un nouveau délai pour quitter la Suisse qui n'aurait pas été respecté, avant de le mettre en détention le 12 juin 2012 (cf. supra). Aucun élément ne permet non plus de retenir que, depuis son retour en Suisse, les autorités aient ordonné au recourant de faire des démarches concrètes en vue de se procurer des papiers d'identité et qu'il n'aurait pas obtempéré. En outre, le recourant affirme, sans être nullement contredit par les autorités cantonales, avoir séjourné depuis son retour en Suisse en 2011 dans les structures d'accueil pour les réfugiés du Valais et avoir ainsi été à disposition des autorités sans chercher à se soustraire, jusqu'à sa mise en détention le 12 juin 2012. Enfin, le dossier ne contient aucun élément établissant que le recourant aurait commis des actes répréhensibles et qu'il ait fait l'objet d'enquêtes ou de condamnations pénales, dont il pourrait chercher à se soustraire en passant dans la clandestinité s'il était libéré.
Entendu le 10 septembre 2012 par le Juge unique, le recourant a indiqué qu'il n'avait pas entrepris de démarches pour prouver son identité, car les autorités suisses lui auraient dit qu'elles s'en chargeaient. Il a déclaré être d'accord de retourner dans son pays, si les autorités l'acceptaient. Du reste, comme il le soutient dans son recours, ce n'est pas la première fois qu'il fait cette déclaration aux autorités.
Quant aux objections formulées par le recourant pour démontrer l'absence d'élément actuel dénotant un risque qu'il passe dans la clandestinité, le Juge unique ne les a pas examinées, considérant, de façon surprenante, qu'elles n'étaient pas pertinentes. Or, le juge de la prolongation de la détention administrative doit aussi vérifier que les motifs justifiant la détention sont (toujours) réalisés.
En pareilles circonstances, on ne voit pas quel élément tangible permettrait d'en inférer que le recourant serait sur le point de partir dans la clandestinité et/ou n'accepterait pas de se rendre dans le pays qui l'accepterait sur son sol.
4.2 L'arrêt attaqué mentionne également l'art. 76 al. 1 let. b ch. 5 LEtr en tant que motif pour la détention. Cette disposition (aussi bien dans son ancienne version que dans sa version en vigueur depuis le 29 septembre 2012 [RO 2012 5359]), suppose entre autres que le renvoi soit imminent. Dès lors que, selon l'information transmise par le Service cantonal (cf. art. 99 al. 1 LTF; consid. 2 supra), les autorités du Turkménistan ont refusé d'accorder un laissez-passer en faveur du recourant et que de nouvelles démarches viennent seulement d'être entamées auprès des autorités russes, on ne voit pas que cette condition soit remplie. Au demeurant, la durée de la détention visée à l'art. 76 al. 1 let. b ch. 5 LEtr ne saurait excéder 30 jours (art. 76 al. 2, 1ère phr., LEtr).
4.3 Enfin, les faits constatés ne permettent pas de retenir l'existence d'un autre motif de mise en détention en vue du renvoi parmi la liste énumérée à l'art. 76 al. 1 let. b LEtr : en particulier, on ne voit pas que le recourant remplisse un des cas de figure énumérés à l'art. 75 LEtr auxquels l'art. 76 al. 1 let. b ch. 1 LEtr renvoie. En outre, la décision de non-entrée en matière fondée sur l'art. 32 al. 2 let. a LAsi prononcée à l'encontre du recourant date du 3 septembre 2009; trois ans s'étant écoulés depuis lors, la détention ne peut plus se fonder sur ce seul élément en vertu de l'art. 76 al. 1 let. b ch. 2 LEtr (cf. ATF 130 II 488 consid. 3.3 p. 491). Comme déjà indiqué, aucun indice concret ne permet de retenir que le recourant se refuserait à obtempérer aux instructions des autorités au sens de l'art. 76 al. 1 let. b ch. 4 LEtr. Enfin, le recourant ne remplit pas les conditions de l'art. 76 al. 1 let. b ch. 6 LEtr.
4.4 Il en découle que la détention administrative du recourant ne repose, en l'état, sur aucun des motifs énumérés à l'art. 76 al. 1 let. b LEtr, de sorte que celle-ci doit être qualifiée d'illicite. Partant, le recours doit être admis et le recourant doit être libéré immédiatement.
5. Compte tenu de l'issue du litige, il n'y a pas lieu de percevoir de frais judiciaires (cf. art. 66 al. 1 et 4 LTF). L'Etat du Valais sera condamné à verser au mandataire du recourant une indemnité de dépens pour la procédure devant le Tribunal fédéral (art. 68 al. 1 et 2 LTF). La requête d'assistance judiciaire devient ainsi sans objet.
Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est admis et l'arrêt du 10 septembre 2012 est annulé.
2. Le recourant est immédiatement libéré.
3. Le canton du Valais versera au mandataire du recourant une indemnité de 2'000 fr. à titre de dépens.
4. La demande d'assistance judiciaire est sans objet.
5. Le présent arrêt est communiqué au recourant, au Service de la population et des migrations, au Juge unique de la Cour de droit public du Tribunal cantonal du canton du Valais et à l'Office fédéral des migrations.
Lausanne, le 30 octobre 2012
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: Zünd
Le Greffier: Chatton