Faits:
A. Citoyen russe né le 10 juin 1989, A._ est titulaire depuis 1999 d'une autorisation de séjour en Suisse, où il réside avec ses parents à Anzère (Valais).
Le 21 juin 2010, à l'occasion d'un contrôle effectué par la police cantonale vaudoise sur l'autoroute A9, il a présenté aux agents un permis de conduire russe délivré le 29 octobre 2008 pour la catégorie B. Ce document a été saisi par la police. Le 17 janvier 2011, le Tribunal de police de l'arrondissement de l'Est vaudois a, sur appel, libéré A._ des fins de la poursuite pénale engagée contre lui pour avoir conduit avec un permis étranger alors qu'il devait se procurer un permis suisse.
B. Par décision du 31 août 2010, le Service de la circulation routière et de la navigation du canton du Valais (ci-après: le SCN) a refusé d'échanger le permis de conduire russe de A._ et lui a interdit de faire usage de son permis étranger sur le territoire suisse. Le recours que l'intéressé a interjeté auprès du Conseil d'Etat contre cette décision a été rejeté le 17 août 2011.
Par arrêt du 23 décembre 2011, la Cour de droit public du Tribunal cantonal du Valais a rejeté le recours formé en personne par A._ contre la décision du Conseil d'Etat. En substance, les juges cantonaux ont considéré que A._ avait obtenu son permis de conduire russe alors qu'il était domicilié en Suisse; dans ces circonstances, la validité de ce permis ne pouvait être admise sur le territoire suisse et, partant, les conditions d'échange de ce document contre un permis de conduire suisse n'étaient pas réunies.
C. A._ recourt en personne par acte du 6 février 2012 auprès du Tribunal fédéral. Il conclut à la restitution de son permis de conduire russe et à l'échange de ce permis contre un permis suisse. A l'appui de son recours, il dépose diverses pièces figurant déjà au dossier ainsi que plusieurs pièces relatives à sa situation financière, dont une lettre de ses parents attestant qu'ils le soutiennent financièrement.
Le Tribunal cantonal et le SCN renoncent à se déterminer. Le Conseil d'Etat et l'Office fédéral des routes concluent au rejet du recours.
Considérant en droit:
1. Le Tribunal fédéral examine d'office et librement la recevabilité des recours qui lui sont soumis (ATF 138 III 46, consid. 1 p. 46).
1.1 Dans un acte intitulé "recours ordinaire simultané", le recourant indique qu'il dépose un recours en matière civile et un recours constitutionnel subsidiaire. Le recours est dirigé contre une décision prise en dernière instance cantonale de refus de convertir un permis de conduire étranger en permis de conduire suisse. C'est donc la voie du recours en matière de droit public au sens des art. 82 ss LTF qui est ouverte dans la mesure où aucun motif d'exclusion au sens de l'art. 83 LTF n'entre en considération.
L'intitulé erroné d'un recours ne nuit pas à son auteur, pour autant que les conditions de recevabilité du recours qui aurait dû être interjeté soient réunies. Encore faut-il qu'il soit possible de convertir le recours dans son ensemble (ATF 134 III 379 consid. 1.2 p. 382 et les arrêts cités). C'est le cas en l'espèce et l'écriture déposée par le recourant peut être traitée comme un recours en matière de droit public.
1.2 Déposé en temps utile (art. 100 al. 1 LTF) par le destinataire de l'arrêt attaqué qui a un intérêt digne de protection à l'annulation ou à la modification de celui-ci (art. 89 al. 1 LTF), le présent recours est recevable.
2. En vertu de l'art. 42 al. 1 LTF, les mémoires de recours doivent être motivés. Selon l'art. 42 al. 2 LTF, les motifs doivent exposer succinctement en quoi l'acte attaqué viole le droit. Pour satisfaire à cette exigence, il appartient au recourant de discuter au moins brièvement les considérants de la décision litigieuse (ATF 134 II 244 consid. 2.1 p. 245). En particulier, la motivation doit se rapporter à l'objet du litige tel qu'il est circonscrit par la décision attaquée (ATF 133 IV 119 consid. 6.4 p. 121). Les griefs de violation des droits fondamentaux et des dispositions de droit cantonal sont en outre soumis à des exigences de motivation accrues (art. 106 al. 2 LTF). La partie recourante doit alors mentionner les principes constitutionnels qui n'auraient pas été respectés et expliquer de manière claire et précise en quoi ces principes auraient été violés; de même, elle doit citer les dispositions du droit cantonal dont elle se prévaut et démontrer en quoi ces dispositions auraient été appliquées arbitrairement ou d'une autre manière contraire au droit (ATF 136 II 489 consid. 2.8 p. 494).
3. Dans un premier moyen, le recourant se plaint de l'absence d'indication des voies de droit dans la décision présidentielle du 26 septembre 2011.
L'art. 112 al. 1 LTF prescrit le contenu minimal des décisions pouvant faire l'objet d'un recours devant le Tribunal fédéral. En fait partie l'indication des voies de droit (let. d).
La décision rendue par le Président de la cour cantonale le 26 septembre 2011 est une demande d'avance de frais. Aucune indication des voies de recours n'y a été apposée parce qu'une telle décision n'est pas susceptible de recours. En effet, comme le Tribunal fédéral a déjà eu l'occasion de l'exposer au recourant dans l'arrêt d'irrecevabilité rendu sur recours contre cet acte, la partie qui peut solliciter une dispense de l'avance de frais doit faire usage de cette possibilité et ne peut saisir directement le Tribunal fédéral d'un recours contre la décision qui l'invite à s'acquitter d'une telle avance (arrêt 1C_479/2011 du 3 novembre 2011 consid. 2). La cour cantonale n'a dès lors pas violé l'art. 112 al. 1 let. d LTF en n'indiquant pas de voies de droit dans l'acte en question.
4. Le recourant se plaint ensuite d'une violation des art. 29 et 29a Cst., 97 et 117 CPC, 28 et 29 al. 1 LPJA/VS.
4.1 Le recourant prétend tout d'abord ne pas avoir été informé sur le montant probable des frais de justice ni sur le droit à l'assistance judiciaire.
4.1.1 La loi valaisanne sur la procédure et la juridiction administratives (LPJA/VS; RS/VS 172.6) régit la procédure suivie pour les affaires administratives relevant de l'administration et de la juridiction administrative (art. 1 al. 1 LPJA/VS). L'art. 81 LPJA/VS renvoie subsidiairement, pour la procédure applicable devant la juridiction administrative, aux dispositions du code de procédure civile. La loi cantonale ne traitant pas des frais, cet aspect est régi par les art. 95 ss du CPC.
4.1.2 L'art. 97 CPC prévoit que le tribunal informe la partie qui n'est pas assistée d'un avocat sur le montant probable des frais et sur l'assistance judiciaire. En l'espèce, le 26 septembre 2011, le Tribunal cantonal a adressé au recourant une demande d'avance de frais de 1'000 francs. Le recourant a de la sorte été informé du montant supposé des frais, qui se sont finalement élevés à 800 francs. S'agissant de l'assistance judiciaire, le recourant ne démontre pas avoir été dans l'ignorance de la possibilité de la demander. Au contraire, il a formellement requis l'assistance judiciaire auprès du Tribunal cantonal, de sorte que, s'il y a eu un manque d'information sur ce point, celui-ci est demeuré sans conséquences.
4.2 Le recourant conteste par ailleurs le refus d'octroi de l'assistance judiciaire qui l'aurait selon lui privé de son droit d'accès à la justice. Il se plaint également du fait que la décision d'assistance judiciaire a été rendue en même temps que la décision au fond.
4.2.1 Aux termes de l'art. 29 al. 3 Cst., toute personne qui ne dispose pas des ressources suffisantes a droit à l'assistance judiciaire gratuite, à moins que sa cause ne paraisse dépourvue de toute chance de succès. Il appartient au requérant d'indiquer d'une manière complète et d'établir - dans la mesure du possible - ses revenus, sa situation de fortune et ses charges; il faut mettre en balance, d'une part, la totalité des ressources effectives du requérant et, d'autre part, l'ensemble de ses engagements financiers (ATF 135 I 221 consid. 5.1 et les arrêts cités). Au surplus, le devoir de l'État de fournir l'assistance judiciaire est subsidiaire à l'obligation d'entretien découlant du droit de la famille (ATF 135 I 91 consid. 2.4.2.2 p. 96; 127 I 202 consid. 3b p. 205; 119 Ia 11 consid. 3a p. 12).
Le droit valaisan reprend ces mêmes critères à l'art. 2 de la loi sur l'assistance judiciaire (LAJ/VS; RS/VS 177.7), selon lequel une personne a droit à l'assistance judiciaire lorsqu'elle ne dispose pas de ressources suffisantes et que sa cause ne paraît pas dépourvue de toute chance de succès. La procédure est régie par la LPJA/VS et subsidiairement par l'ordonnance du Conseil d'Etat (art. 7 LAJ/VS). Celui-ci a adopté sur cette base l'ordonnance sur l'assistance judiciaire (OAJ/VS; RS/VS 177.700), à teneur de laquelle le requérant doit justifier de sa situation de fortune et de ses revenus, notamment en déposant sa dernière décision de taxation en force sur le revenu et la fortune (art. 4 al. 2 OAJ/VS).
L'art. 117 CPC invoqué par le recourant est en revanche sans pertinence dès lors qu'il n'y a pas matière ici à une application subsidiaire du CPC (art. 81 LPJA/VS).
4.2.2 En l'espèce, le Tribunal cantonal, se référant à la LAJ/VS, a constaté que les pièces produites par le recourant, relatives à son statut de personne sans activité lucrative, aux dépenses consenties pour ses études et au soutien financier de ses parents, ne suffisaient pas à établir son impécuniosité; bien qu'informé de ce que sa situation devait s'apprécier au vu des taxations fiscales, le recourant ne les a jamais produites. La cour cantonale a aussi relevé que la seconde condition d'octroi de l'assistance judiciaire n'était pas respectée, la cause étant d'emblée vouée à l'échec.
Le recourant se contente d'affirmer que le Tribunal cantonal n'a pas examiné sa situation financière. Il méconnaît que les informations qu'il avait transmises ont été retenues et ne fait que les répéter. Il n'expose pas pourquoi il n'a pas transmis les documents requis ni les raisons pour lesquelles l'appréciation des juges cantonaux violerait le droit. Il ne tente pas non plus de démontrer que son recours n'était pas d'emblée voué à l'échec. Il est ainsi douteux que son grief respecte les exigences de motivation accrues de l'art. 106 al. 2 LTF. Quoi qu'il en soit, le résultat auquel parvient le Tribunal cantonal dans son examen d'octroi de l'assistance judiciaire au recourant n'est pas entaché d'arbitraire. En effet, alors même que celui-ci se prévaut de sa situation d'étudiant entièrement à la charge de ses parents, il n'a donné aucune information sur leur situation financière. Quant au droit d'accès à la justice, il n'a pas été violé puisqu'une décision au fond a été rendue.
Pour le reste, le recourant ne démontre pas non plus en quoi le fait que la juridiction de recours statue sur l'assistance judiciaire en même temps que sur le fond contreviendrait au droit. Excepté pour certains cas très particuliers dans lesquels des démarches procédurales doivent encore être entreprises, cette pratique est généralement admise (arrêts 2D_3/2011 du 20 avril 2011 consid. 2.4; 9C_463/2009 du 8 juillet 2009 consid. 3.3.2; 4P.300/2005 du 15 décembre 2005 consid. 3.1). C'est par ailleurs ainsi que procède usuellement le Tribunal fédéral (cf. CORBOZ, in Commentaire de la LTF, 2009, n° 67 ad art. 64 LTF).
4.3 Enfin, le recourant fait valoir une violation de l'art. 28 LPJA/VS (disposition qui renvoie subsidiairement, en matière de preuve, au CPC et au CPP) de la part de la cour cantonale qui aurait refusé d'appliquer le CPC. Le recourant n'explique pas en quoi consiste cette violation de sorte que le grief est irrecevable (art. 42 al. 2 LTF; cf. consid. 2 ci-dessus).
5. On comprend ensuite de l'argumentation du recourant qu'il se plaint d'une violation de son droit d'être entendu.
5.1 Selon lui, le Tribunal cantonal n'aurait pas statué sur son moyen relatif à la durée prétendument excessive de la procédure. Il explique en réalité ne pas avoir compris si le Tribunal a admis son grief ou non. Or, le considérant 2a de l'arrêt attaqué est clair sur ce point. En dépit des doutes à ce sujet, la cour cantonale a laissé indécise la question de savoir si le grief soulevé satisfaisait aux exigences formelles de motivation du droit cantonal. Se référant à sa propre jurisprudence, elle a en revanche bien expliqué que, lorsque la décision dont le justiciable se plaint qu'elle tarde à intervenir est rendue pendant l'instruction du recours, celui-ci devient sans objet. Elle a donc considéré que, la cause du recourant ayant fait l'objet d'une décision, il n'y avait plus d'intérêt à invoquer la violation du principe de célérité. Ainsi, le tribunal a bien examiné cette question, mais l'a tenue pour non pertinente à ce stade de la procédure. Il n'y a donc pas de violation du droit d'être entendu du recourant.
5.2 Le recourant se plaint également d'une violation de l'art. 23 al. 1 LCR en raison du fait qu'il n'aurait pas eu l'occasion de s'exprimer avant que le SCN rende sa décision.
L'art. 23 al. 1 in fine LCR prévoit que, "en règle générale, l'autorité entendra l'intéressé avant de lui retirer son permis de conduire ou de le soumettre à une interdiction de circuler". En matière de droit d'être entendu, cette disposition n'offre pas plus de garanties que l'art. 29 al. 2 Cst. (arrêt 6A.12/2003 du 2 avril 2003 consid. 2.4). A l'instar de la garantie constitutionnelle, l'art. 23 LCR ne confère pas à l'intéressé le droit d'être entendu oralement, mais uniquement le droit de s'exprimer le plus largement possible sur tout point pertinent pour la cause (RENÉ SCHAUFFAUSER, Grundriss des schweizerischen Strassenverkehrsrechts, Bd III, 1995, pp. 457 s. n. 2714).
Le recourant persiste à confondre la présente procédure, par devant les autorités valaisannes, relative au refus d'échanger son permis de conduire russe contre un permis suisse, avec la procédure pénale, par devant les autorités vaudoises, qui s'est déroulée en application de l'art. 147 de l'ordonnance du 27 octobre 1976 réglant l'admission des personnes et des véhicules à la circulation routière (Ordonnance réglant l'admission à la circulation routière, OAC; RS 741.51). Dans la présente procédure, le recourant a été invité le 2 août 2010 par le SCN à s'exprimer sur le refus envisagé d'échange de permis. Celui-là y a donné suite en adressant audit service le 16 août suivant une correspondance de deux pages dans laquelle il exposait son point de vue. Son droit d'être entendu a ainsi été respecté, étant souligné que ce droit n'implique pas de pouvoir s'exprimer oralement.
6. Le recourant fait en outre grief au Tribunal cantonal d'avoir déformé les faits.
6.1 Le Tribunal fédéral statue en principe sur la base des faits établis par l'autorité précédente (art. 105 al. 1 LTF), sous réserve des cas prévus à l'art. 105 al. 2 LTF. Selon l'art. 97 LTF, il ne peut s'en écarter que si les constatations de ladite autorité ont été établies en violation du droit au sens de l'art. 95 LTF ou de façon manifestement inexacte, c'est-à-dire arbitraire (art. 105 al. 2 LTF) et pour autant que la correction du vice soit susceptible d'influer sur le sort de la cause (ATF 137 I 58 consid. 4.1.2 p. 62; 136 II 304 consid. 2.4 p. 314). Si le recourant entend se prévaloir de constatations de faits différentes de celles de l'autorité précédente (cf. art. 97 al. 1 LTF), il doit expliquer de manière circonstanciée en quoi les conditions d'une exception prévue par l'art. 105 al. 2 LTF seraient réalisées. A défaut, il n'est pas possible de tenir compte d'un état de fait divergent de celui retenu dans l'acte attaqué. 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 (ATF 136 II 101 consid. 3 p. 104 et les arrêts cités).
6.2 Les éléments par lesquels le recourant entend compléter l'état de fait ont pour certains été retenus par le Tribunal cantonal (ainsi le fait qu'il a été libéré de toute accusation sur le plan pénal). D'autres sont sans pertinence pour l'issue de la cause (ainsi le fait que la voiture au volant de laquelle il a été interpelé appartiendrait à sa mère et non à une société anonyme, le fait que son permis de séjour n'était pas en voie de renouvellement mais avait été "suspendu" et le fait que la préfecture d'Aigle lui a remboursé l'amende infligée). D'autres encore ne relèvent pas de l'état de fait mais de l'appréciation du Tribunal cantonal (ainsi le défaut de pertinence de la décision des autorités pénales). Quoi qu'il en soit, le recourant n'invoque aucun arbitraire dans la présentation des faits et sa critique n'est pas suffisante au regard des exigences légales et jurisprudentielles rappelées ci-dessus.
Le recours apparaît ainsi irrecevable sur ce point.
7. Au fond, le recourant fait encore valoir une violation de l'art. 147 al. 1 LCR [recte: OAC]. Il se réfère aux art. 16 al. 1 et 22 al. 1 LCR, 42 al. 4 et 45 al. 1 OAC ainsi que 41 al. 6 let. a de la Convention du 8 novembre 1968 sur la circulation routière qui, selon lui, seraient applicables aux mêmes cas que l'art. 147 al. 1 OAC. Dès lors que les autorités pénales l'ont libéré de cette infraction, les autres dispositions ne lui seraient par conséquent pas applicables. Le recourant se plaint également de ce que le renvoi en fin d'arrêt à l'art. 44 al. 1 LSR [recte: LCR] serait peu clair.
7.1 Les art. 42 ss OAC édictent les circonstances dans lesquelles le titulaire d'un permis de conduire étranger doit se procurer un permis suisse et les conditions auxquelles cet échange peut se faire. L'art. 147 al. 1 OAC prescrit que celui qui aura conduit un véhicule en étant titulaire d'un permis de conduire étranger alors qu'il aurait dû se procurer un permis suisse sera puni de l'amende. Cette disposition prévoit la sanction pénale applicable dans un tel cas.
7.1.1 Les procédures pénale et administrative poursuivent des buts différents (SCHAUFFAUSER, op. cit., p. 422 n. 2640). Alors que la sanction pénale tend à punir l'auteur d'une infraction, la mesure administrative a pour objectif de garantir la sécurité des usagers de la route (cf. ATF 137 I 363 consid. 2.4 p. 369). L'autorité administrative ne peut en principe s'écarter du jugement pénal qu'à certaines conditions, notamment si elle est en mesure de fonder sa décision sur des constatations de fait que le juge pénal ne connaissait pas ou qu'il n'a pas prises en considération ou s'il n'a pas élucidé toutes les questions de droit (ATF 137 I 363 consid. 2.3.2 p. 368; 136 II 447 consid. 3.1 p. 451 et les arrêts cités).
7.1.2 En l'espèce, les autorités cantonales se sont penchées sur les conditions auxquelles le permis de conduire russe du recourant pouvait être échangé contre un permis de conduire suisse. L'objectif n'est donc pas de juger les faits du 21 juin 2010 ni de sanctionner le recourant pour avoir conduit avec son permis russe. Le Tribunal cantonal a ainsi relevé à juste titre que la date à partir de laquelle le permis étranger avait été utilisé était sans pertinence. Dans la présente cause, administrative, les autorités devaient déterminer de manière générale si le recourant remplit les conditions de délivrance d'un permis de conduire suisse. Ces conditions sont indépendantes non seulement de toute condamnation pénale, mais encore de toute infraction aux règles de la circulation routière. Il s'agit notamment de la validité du permis étranger, elle-même déterminée en fonction du domicile du conducteur lors de l'obtention du permis (art. 44 OAC et 22 al. 1 LCR), éléments que le juge pénal n'a pas examinés.
Dans ces circonstances, le juge administratif examine de manière autonome la validité du permis de conduire russe à échanger contre un permis suisse, indépendamment de l'appréciation du juge pénal sur l'infraction de l'art. 147 OAC.
7.2 Pour le reste, le recourant énumère les dispositions légales que la cour cantonale a appliquées. Alors que les considérants de l'arrêt attaqué font l'objet d'une argumentation circonstanciée, le recourant n'expose aucune critique à leur encontre. Le grief dirigé contre l'application de ces articles ne satisfait ainsi pas aux exigences minimales de motivation de l'art. 42 al. 2 LTF et est dès lors irrecevable (consid. 2 ci-dessus).
Il en va de même du grief selon lequel le renvoi à l'art. 44 al. 1 LCR serait peu clair, voire "bâclé", comme le recourant le prétend. Ici encore, le moyen apparaît insuffisamment motivé. On peut tout au plus comprendre la confusion du recourant du fait que l'arrêt attaqué, par une simple erreur de plume, se réfère erronément à l'art. 44 LCR alors qu'il est question de l'art. 44 OAC. Quoi qu'il en soit, le raisonnement très détaillé des juges cantonaux permet d'identifier facilement la disposition appliquée, savoir l'art. 44 OAC, dont le contenu est au demeurant expressément cité. Cet article fixe les conditions auxquelles le titulaire d'un permis national étranger valable peut recevoir un permis de conduire suisse pour la même catégorie de véhicules. A juste titre, les instances précédentes ont tout d'abord examiné si le recourant était titulaire d'un permis national étranger valable au sens du droit suisse, dont il serait ainsi à même de demander l'échange. C'est donc bien l'art. 44 OAC qui est pertinent en l'espèce, ce qui suffit à écarter la critique du recourant - à supposer qu'elle soit recevable -, dirigée uniquement contre le principe même de l'application de cette disposition et non contre la manière dont elle a été appliquée.
8. Le recourant a pris une conclusion en restitution de son permis de conduire russe. Cette conclusion est manifestement étrangère à l'objet du litige qui porte sur le refus d'échanger le permis de conduire russe du recourant contre un permis de conduire suisse et sur l'interdiction de faire usage du permis de conduire russe. La restitution du permis russe n'est au demeurant pas litigieuse puisque le Tribunal cantonal a constaté que le SCN tenait ce document à la disposition du recourant. Cette conclusion est partant irrecevable.
9. Il résulte de ce qui précède que le recours doit être rejeté. L'assistance judiciaire ne peut être accordée au recourant, qui, comme on l'a vu ci-dessus, n'a pas démontré son indigence, et dont les conclusions paraissaient d'emblée vouées à l'échec (art. 64 al. 1 LTF). Les frais judiciaires sont mis à la charge du recourant (art. 66 al. 1 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. Les frais judiciaires, arrêtés à 1'000 fr., sont mis à la charge du recourant.
4. Le présent arrêt est communiqué au recourant, ainsi qu'au Service de la circulation routière et de la navigation, au Conseil d'Etat, au Tribunal cantonal du canton du Valais, Cour de droit public, et à l'Office fédéral des routes.
Lausanne, le 22 novembre 2012
Au nom de la Ire Cour de droit public
du Tribunal fédéral suisse
Le Juge présidant: Merkli
La Greffière: Sidi-Ali