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. 