Faits:
A. Le 10 mai 2011, l'Office cantonal de la population du canton de Genève (ci-après l'Office cantonal) a informé X._, ressortissant français, de son intention de prononcer son renvoi de Suisse et l'a invité à se déterminer dans un délai de 10 jours. Par courrier daté du 23 mai 2011, X._ a sollicité une prolongation de ce délai.
Le 24 mai 2011, l'Office cantonal a prononcé le renvoi de Suisse de X._ notamment en raison d'une peine privative de liberté de six ans qui lui avait été infligée le 4 novembre 2009 et confirmée le 1er juin 2010. La décision a été déclarée exécutoire nonobstant recours.
X._ a recouru au Tribunal administratif de première instance de Genève (ci-après le Tribunal de première instance) contre la décision du 24 mai 2011.
B. Le 1er juin 2011, X._ a requis l'assistance juridique pour la procédure de recours devant le Tribunal de première instance, se plaignant d'une violation de son droit d'être entendu et d'une appréciation erronée des faits pertinents. Par décision du 12 août 2011, le Vice-président du Tribunal civil a rejeté la requête d'assistance juridique de X._. Il a considéré que le recours à l'encontre de la décision de renvoi prononcée par l'Office cantonal était dépourvu de chance de succès. Il a retenu en particulier que la violation du droit d'être entendu invoquée par le recourant n'était pas établie et pouvait, au demeurant, être réparée dans la procédure de recours.
Le 5 septembre 2011, X._ a recouru contre la décision du 12 août 2011, demandant à titre préalable que son audition soit ordonnée. La procuration en faveur de son conseil n'ayant pas été reçue dans le délai imparti, la Vice-présidente de la Cour de justice du canton de Genève (ci-après le Cour de justice) a déclaré ce recours irrecevable.
X._ ayant signalé que la procuration avait par erreur été produite au greffe du Tribunal de première instance, la Vice-présidente de la Cour de justice a, par décision du 8 février 2012, annulé la décision d'irrecevabilité et, statuant sur le fond, rejeté le recours de X._ contre le refus de lui octroyer l'assistance juridique prononcé le 12 août 2011, sans se prononcer sur la demande d'audition du recourant.
C. Par acte du 21 février 2012, X._ dépose un recours constitutionnel subsidiaire au Tribunal fédéral contre la décision du 8 février 2012. Il conclut, à titre principal, à l'annulation de la décision attaquée et à ce que le bénéfice de l'assistance juridique lui soit accordé pour la procédure de recours devant le Tribunal de première instance. Subsidiairement, il demande que le dossier soit retourné à l'autorité cantonale pour nouvelle décision au sens des considérants. Il requiert en outre le bénéfice de l'assistance judiciaire pour la procédure devant le Tribunal fédéral.
Le Tribunal de première instance, la Vice-présidence du Tribunal civil et l'Office cantonal ont renoncé à déposer des observations. La Vice-présidente de la Cour de justice a déposé sa détermination en date du 28 mars 2012 et persisté dans les termes de la décision querellée.
X._ a déposé d'ultimes observations le 23 avril 2012.
D. Le 25 juin 2012, au terme d'un échange de vues au sens de l'<ref-law>, les Cours qui se sont prononcées ont approuvé l'interprétation de l'art. 10 al. 3 de la loi genevoise sur la procédure administrative du 12 septembre 1985 (RS-GE E 5 10) proposée.

Considérant en droit:
1. 1.1 La décision attaquée, rendue sur recours, confirme le rejet de la demande d'assistance juridique formée par le recourant. Il s'agit donc d'une décision incidente notifiée séparément qui peut faire l'objet d'un recours immédiat auprès du Tribunal fédéral en vertu de l'<ref-law>, applicable par renvoi de l'<ref-law>. En effet, selon la jurisprudence, le refus d'accorder l'assistance judiciaire est de nature à causer un préjudice irréparable au sens de la disposition précitée (cf. arrêt 2D_25/2009 du 25 mai 2009 consid. 1.1 et les arrêts cités).
1.2 La détermination de la voie de droit ouverte à l'encontre d'une décision incidente dépend de la cause au fond (cf. arrêt 2D_32/2010 du 8 octobre 2010 consid. 1.2 et les arrêts cités). En l'occurrence, la décision sur l'assistance judiciaire a été rendue en relation avec le prononcé du renvoi du recourant de Suisse en application de l'art. 64 LEtr. En vertu de l'art. 83 let. c ch. 4 LTF, la voie du recours en matière de droit public est exclue en ce domaine. C'est donc à juste titre qu'un recours constitutionnel subsidiaire a été formé (cf. <ref-law>).
1.3 Interjeté en temps utile (art. 117 et 100 al. 1 LTF) et dans les formes prévues par la loi (<ref-law>) par la partie qui, se voyant refuser le bénéfice de l'assistance judiciaire, dispose d'un intérêt juridique à recourir (<ref-law>), le recours est en principe recevable, dès lors que la décision entreprise émane d'une autorité judiciaire cantonale supérieure statuant en dernière instance (art. 114 et 86 al. 1 let. d et al. 2 LTF).
1.4 Le recours constitutionnel subsidiaire ne peut être formé que pour violation des droits constitutionnels (<ref-law>). La qualité pour soulever le grief d'arbitraire par la voie du recours constitutionnel subsidiaire suppose en outre que le recourant puisse se prévaloir d'une situation juridique protégée par la loi ou par un droit fondamental spécifique (cf. <ref-law>; <ref-ruling> consid. 6 p. 197 ss). Le Tribunal fédéral ne se saisit enfin que des griefs soulevés et motivés de façon détaillée par la partie recourante (art. 106 al. 2 et 117 LTF).
2. Le recourant invoque différents griefs de nature matérielle et formelle. Sur le plan formel, il conteste notamment la compétence de la Vice-présidente de la Cour de justice de rendre la décision attaquée. Dès lors que l'incompétence de l'autorité qui a rendu une décision peut, si elle est manifeste, entraîner la nullité de celle-ci (cf. arrêt 1C_235/2008 du 13 mai 2009 consid. 3.2.1; <ref-ruling> consid. 5.6 p. 218 s.), il convient de commencer par l'examen de ce grief.
2.1 Invoquant la protection conférée par l'art. 30 al. 1 Cst., le recourant allègue qu'en tant qu'elle émane de la Vice-présidente de la Cour de justice, la décision attaquée n'a pas été rendue sur la base d'une délégation conforme au droit. Il se prévaut dans ce contexte d'une application arbitraire des art. 25 et 29 al. 5 de la loi genevoise sur l'organisation judiciaire du 26 septembre 2010 (LOJ/GE, RS-GE E 2 05). Il estime que, dans la mesure où, aux termes de l'art. 29 al. 5 LOJ/GE, le vice-président exerce les compétences qui lui sont déléguées par le président dans les limites du règlement de la juridiction, il ne pourrait agir sur la base d'une telle délégation du président en l'espèce, puisque le règlement de la Cour de justice n'a pas encore été publié au recueil systématique de la législation genevoise (art. 25 al. 3 LOJ/GE).
2.2 En vertu de l'art. 30 al. 1 Cst., toute personne dont la cause doit être jugée dans une procédure judiciaire a droit à ce qu'elle soit portée devant un tribunal établi par la loi, compétent, indépendant et impartial. Le droit des parties à une composition régulière du tribunal impose des exigences minimales en procédure cantonale. C'est en premier lieu à la lumière des règles cantonales applicables d'organisation et de procédure qu'il convient d'examiner si une autorité judiciaire ou administrative a statué dans une composition conforme à la loi. Sur ce point, le pouvoir d'examen du Tribunal fédéral est limité à l'arbitraire (cf. <ref-ruling> consid. 2.1.2.1 p. 34 s.)
Selon l'art. 10 al. 3 de la loi genevoise sur la procédure administrative du 12 septembre 1985 (LPA/GE, RS-GE E 5 10), il appartient au président de la Cour de justice de connaître des recours contre les décisions de refus ou de retrait de l'assistance juridique prises en première instance. Lorsque le président du tribunal est empêché ou récusé, il est remplacé par le vice-président ou, s'agissant de la Cour de justice et du Tribunal civil, par le premier en rang des vice-présidents (cf. art. 32 al. 1 LOJ/GE). Cette règle de remplacement de nature générale étant fixée directement dans la loi, elle n'a pas besoin d'être précisée dans le règlement de la juridiction.
2.3 En l'espèce, la décision attaquée a été prise par la Vice-présidente la plus ancienne en rang de la Cour de justice. Celle-ci a par conséquent statué conformément à la règle de compétence précitée applicable en cas d'empêchement ou de récusation du président. Dans ces conditions, le grief d'application arbitraire des règles de composition des autorités judiciaires doit être rejeté.
3. Invoquant l'arbitraire et une violation de son droit d'être entendu constitutive d'un déni de justice, le recourant, qui avait conclu à titre préalable dans son recours cantonal à ce que son audition soit ordonnée, soutient qu'en vertu de l'art. 10 al. 3 LPA/GE, la Vice-présidente de la Cour de justice ne pouvait rendre une décision en matière d'assistance juridique le 8 février 2012, sans l'avoir invité à faire savoir s'il souhaitait être entendu ou exposer les motifs pour lesquels elle considérait qu'il n'avait pas à être entendu. Il se réfère à la jurisprudence rendue par le Tribunal fédéral en relation avec l'art. 143A al. 2 de l'ancienne loi genevoise sur l'organisation judiciaire du 22 novembre 1941 (aLOJ/GE). Il ajoute que, dans la mesure où la décision attaquée est muette sur le sujet, l'instance cantonale a violé le droit à une décision motivée découlant des art. 29 al. 1 et 2 Cst.
3.1 Selon l'art. 10 al. 3 LPA/GE, "en cas de refus ou de retrait de l'assistance juridique, la personne qui l'a sollicitée peut recourir par écrit dans les 30 jours dès la notification de la décision auprès du président de la Cour de justice. En règle générale, le recourant est entendu". Cette disposition a été introduite par la LOJ/GE, entrée en vigueur le 1er janvier 2011. Dans la mesure où l'art. 10 al. 3 LPA/GE reprend la teneur exacte de l'art. 143A al. 3 aLOJ/GE, il faut se demander si la jurisprudence développée à propos de cette dernière disposition s'applique mutatis mutandis à la première.
3.2 En relation avec l'art. 143A al. 3 aLOJ/GE, le Tribunal fédéral a considéré depuis l'arrêt 4P.195/2002 du 13 novembre 2002 que cette disposition allait plus loin que le droit constitutionnel fédéral (art. 29 al. 2 Cst.) en permettant au recourant de faire valoir ses allégués et ses moyens non seulement par écrit, mais aussi oralement. L'audition de l'intéressé en vertu de cette disposition était la règle et non pas l'exception. Elle ne pouvait être refusée que dans des circonstances particulières. Par ailleurs, elle ne dépendait pas d'une requête expresse du recourant, l'absence d'une telle demande n'établissant pas encore une renonciation à ce droit, laquelle devait être établie de manière non équivoque et être entourée d'un minimum de garanties. Cette jurisprudence a été confirmée à plusieurs reprises (cf. arrêts 1P.573/2004 du 2 novembre 2004 consid. 2.2; 5A_496/2009 du 21 octobre 2009 consid. 2.1; 2D_32/2010 du 8 octobre 2010 consid. 3). L'application de l'art. 143A al. 3 aLOJ/GE aurait imposé à la Vice-Présidente de la Cour de justice soit d'entendre le recourant soit à tout le moins d'expliquer en quoi elle considérait que des circonstances particulières justifiaient de ne pas procéder à l'audition requise.
3.3 Dans l'arrêt 1B_171/2011 du 15 juin 2011 publié in SJ 2011 I 489, le Tribunal fédéral s'est prononcé sur la portée de l'art. 10 al. 3 LPA/GE. Il a relevé que, même si elle va apparemment plus loin que le droit d'être entendu découlant de l'art. 29 al. 2 Cst., cette disposition ne pose qu'un principe et ne confère pas un droit absolu à une audition, même en cas de demande de l'intéressé (cf. arrêt précité consid. 4). Dans cette affaire, il a été jugé que la requête du recourant ne devait pas être interprétée comme une demande générale d'audition personnelle, mais comme un simple moyen de preuve invoqué à l'appui d'un allégué déterminé. Or, ce dernier apparaissait sans pertinence. Le refus d'entendre personnellement le recourant n'était donc ni arbitraire, ni constitutif d'une violation du droit d'être entendu garanti par l'art. 29 al. 2 Cst. (cf. arrêt 1B_171/2011 du 15 juin 2011 consid. 4).
On ne peut déduire de cet arrêt que les principes posés à l'art. 143A al. 3 aLOJ/GE ne seraient plus applicables à l'art. 10 al. 3 LPA/GE. En effet, le Tribunal fédéral, qui ne revoit le droit cantonal qu'en fonction des griefs soulevés (cf. <ref-law>), ne s'est pas prononcé sur cette question dans l'arrêt 1B_171/2011. Il a seulement constaté que le recourant ne formulait pas une demande générale d'audition, mais proposait son audition comme moyen de preuve à l'appui d'un allégué déterminé. Par conséquent, la Cour de droit public n'avait pas à se demander si l'ancienne jurisprudence demeurait applicable à l'art. 10 al. 3 LPA/GE. Or, dans la présente affaire, on est bien en présence d'une demande d'audition générale qu'on ne saurait assimiler à une offre de preuve.
3.4 Dès lors que l'arrêt 1B_171/2011 ne se prononce pas sur l'application de la jurisprudence relative à l'art. 143A al. 3 aLOJ/GE à l'art. 10 al. 3 LPA/GE, il convient d'examiner cette question.
Dans son commentaire au projet de loi (PL 10462), le Conseil d'État du canton de Genève expose ce qui suit au sujet de l'art. 10 al. 3 LPA/GE: "La LOJ ne contient que des normes communes aux organes du pouvoir judiciaire. L'assistance juridique traitée en matière pénale dans le CPP et en matière civile dans le CPC n'a plus sa place dans la LOJ. La matière doit néanmoins être réglée dans le domaine administratif. (...) Al. 3 Reprise de l'article 143A, al. 3, LOJ actuelle." (cf. commentaire PL 10462 p. 90). L'art. 10 al. 3 LPA/GE a été adopté par l'organe législatif dans la teneur proposée par l'exécutif. Au vu du commentaire laconique précité, l'on doit admettre que l'intention du législateur était de maintenir, pour l'assistance juridique en matière administrative, la même règle que sous l'ancien droit en ce qui concerne la voie de recours et l'audition du recourant. Du reste, à l'art. 10 al. 4 LPA/GE, le législateur a précisé que les dispositions réglementaires édictées par le Conseil d'État en matière d'assistance juridique s'appliquent pour le surplus. Il en découle a contrario que la règle de l'art. 10 al. 3 LPA/GE, qui pose le principe de l'audition du recourant, demeure valable, peu importe que, pour le reste, le règlement du Conseil d'État sur l'assistance juridique et l'indemnisation des conseils juridiques et défenseurs d'office en matière civile, administrative et pénale du 28 juillet 2010 (RAJ/GE, RS-GE E 2 05.04) prévoie qu'en ce qui concerne la procédure d'instruction, les dispositions du code de procédure civile sont applicables à toute requête d'assistance juridique (cf. art. 8 al. 3 RAJ/GE). Du reste, ces dispositions (cf. <ref-law> [RS 272]) n'excluent pas le principe même d'une audition du recourant en matière d'assistance juridique. Partant, il n'y a pas de raison de considérer que l'interprétation donnée par la jurisprudence de l'art. 143A al. 3 aLOJ/GE ne serait plus applicable à l'art. 10 al. 3 LPA/GE. Selon l'art. 10 al. 3 LPA/GE, saisi d'un recours portant sur l'assistance juridique en matière administrative, le président de la Cour de justice est par conséquent en règle générale tenu d'entendre le recourant. Cette règle n'est cependant pas absolue. Il appartient toutefois au président de la Cour de justice de motiver, le cas échéant, sa décision de renoncer à cette audition. En ce sens, le consid. 4 de l'arrêt 1B_171/2011 n'est pas contraire à la jurisprudence, même s'il a pu entraîner une certaine confusion à cet égard.
3.5 Dans les conclusions figurant en tête de son recours cantonal du 5 septembre 2011, le recourant a demandé, à titre préalable, que son audition soit ordonnée. Dans la décision entreprise du 8 février 2012, la Vice-Présidente de la Cour de justice ne s'est pas prononcée sur cette requête et n'a donc pas exposé les raisons pour lesquelles elle considérait qu'exceptionnellement les circonstances justifiaient de renoncer à l'audition requise. En procédant de la sorte, la Vice-Présidente de la Cour de justice a appliqué arbitrairement l'art. 10 al. 3 LPA/GE. Le grief y relatif doit donc être admis.
3.6 On doit également se demander si l'arrêt querellé n'a pas été rendu en violation de l'art. 29 Cst., comme le soutient le recourant. En effet, selon la jurisprudence, une autorité cantonale de recours commet un déni de justice formel et viole l'art. 29 al. 1 Cst. si elle omet de statuer sur une conclusion du recours dont elle est saisie alors qu'elle est compétente pour le faire. En outre, le droit d'être entendu découlant de l'art. 29 al. 2 Cst. impose à l'autorité de jugement l'obligation de motiver ses décisions (cf. <ref-ruling> consid. 2c p. 34; <ref-ruling> consid. 2b p. 109). Pour satisfaire cette exigence, il suffit toutefois que celle-ci mentionne au moins brièvement les motifs qui l'ont guidée et sur lesquels elle a fondé sa décision (cf. arrêt 1B_656/2011 du 19 décembre 2011 consid. 2.1 et les arrêts cités).
S'agissant d'une demande expresse portant sur la tenue de débats, la Cour de céans a admis, dans un arrêt 2C_276/2011 du 10 octobre 2011 consid. 2.1 non publié à l'<ref-ruling>, qu'il n'y avait pas de violation de l'obligation de motiver bien que l'autorité cantonale ne se soit pas prononcée sur le sujet. La justification en était qu'aucune disposition constitutionnelle n'imposait la tenue de débats publics et que la procédure devant la justice administrative concernée était en principe écrite. Or, les recourants n'avaient fourni aucun motif justifiant leur demande. En conséquence, ils ne pouvaient reprocher au Tribunal cantonal de n'y avoir pas répondu de manière motivée, mais devaient bien plutôt se laisser opposer le fait qu'en statuant sur le fond de leur cause sans donner formellement suite à leur requête, les premiers juges avaient implicitement considéré qu'il n'y avait pas de raison de faire exception à la règle prévoyant que la procédure se déroule par écrit.
Contrairement à l'affaire précitée où la règle était la procédure écrite, le droit cantonal genevois prévoit expressément, à l'art. 10 al. 3 LPA/GE, que la partie qui recourt contre le refus de l'assistance juridique doit en principe être entendue. Or, une autorité qui veut déroger au principe de l'audition qui figure dans la loi pour appliquer l'exception doit motiver sa décision, qui plus est lorsqu'elle est saisie d'une requête expresse demandant l'application de la règle générale. Comme le droit cantonal prévoit le droit pour un recourant d'être entendu en ce qui concerne l'assistance juridique en matière administrative, celui-ci doit être en mesure de comprendre pourquoi il n'a pas été donné suite à une requête qui correspond à la règle posée par la procédure administrative et, partant, de remettre en cause les raisons de ce refus devant le Tribunal fédéral. Une décision qui ne contient aucune précision à cet égard viole l'art. 29 Cst.
3.7 Il découle de ce qui précède que les griefs de nature formelle invoqués en relation avec l'application de l'art. 10 al. 3 LPA/GE et la demande d'audition du recourant sont fondés. Cette conclusion suffit à annuler l'arrêt attaqué sans qu'il soit besoin d'examiner les autres griefs soulevés par le recourant.
4. Dans ces circonstances, il convient d'admettre le recours, d'annuler la décision attaquée et de renvoyer la cause à l'autorité cantonale pour qu'elle rende une nouvelle décision (cf. <ref-law>) après avoir procédé à l'audition du recourant ou motivé dûment pour quelle raison elle renonce à appliquer la règle posée à l'art. 10 al. 3 LPA/GE.
Il ne sera pas perçu de frais judiciaires (<ref-law>). En revanche, le canton de Genève versera des dépens au recourant qui obtient gain de cause sur ses conclusions subsidiaires (art. 68 al. 1 et 2 LTF), ce qui rend sans objet sa requête d'assistance judiciaire dans la présente procédure.

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est admis, la décision attaquée est annulée et la cause est renvoyée à l'autorité précédente pour nouvelle décision dans le sens des considérants.
2. Il n'est pas perçu de frais judiciaires.
3. La requête d'assistance judiciaire est sans objet.
4. Le canton de Genève versera au conseil du recourant une indemnité de CHF 2'000.- à titre de dépens.
5. Le présent arrêt est communiqué au mandataire du recourant, à l'Office cantonal de la population du canton de Genève, au Tribunal administratif de première instance du canton de Genève, au Vice-président du Tribunal civil, Assistance juridique, et à la Vice-présidente de la Cour de justice du canton de Genève, Assistance juridique.
Lausanne, le 31 juillet 2012
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: Zünd
La Greffière: Beti