Faits:
A. Ressortissant algérien né en 1979, X._ a déposé, sous un autre nom, une demande d'asile en Suisse en juin 2001, qui a été radiée en raison de sa disparition.
Le 11 janvier 2003, il a épousé une citoyenne suisse. Le divorce des époux est entré en force le 27 août 2005.
Dès 2001, X._ a été interpellé, écroué et condamné pénalement à de nombreuses reprises. Sa dernière condamnation prononcée le 8 décembre 2008 par la Cour correctionnelle sans jury du canton de Genève portait sur des actes de brigandage et s'élevait à deux ans et quatre mois d'emprisonnement. Le recours déposé contre cette condamnation a été rejeté par la Cour de cassation genevoise le 17 avril 2009 dont l'arrêt est devenu définitif (cf. arrêt du Tribunal fédéral 6B_438/2009 du 28 septembre 2009). Actuellement, X._ purge sa peine, la fin de son emprisonnement étant fixée au 2 mars 2011.
B. Après son mariage, X._ a été mis au bénéfice d'une autorisation de séjour. Par décision du 26 novembre 2004, l'Office cantonal genevois de la population (ci-après l'Office cantonal) a refusé de la renouveler. L'Office fédéral des migrations (ci-après l'Office fédéral) a étendu cette décision à toute la Suisse depuis le 19 janvier 2005. X._ est demeuré en Suisse malgré cette décision.
Le 26 février 2006, l'Office fédéral a prononcé une interdiction d'entrée en Suisse pour une durée de 10 ans à son encontre en raison de ses antécédents judiciaires. Le 20 mars 2006, X._ a été mis en détention administrative en vue de son renvoi, mais son refoulement n'a pas été possible en raison de son opposition physique.
Le 17 février 2009, l'Office cantonal a ordonné le renvoi de Suisse de X._. Le recours déposé contre cette décision a été rejeté par la Commission cantonale de recours en matière administrative du canton de Genève (ci-après la Commission de recours) le 1er décembre 2009.
C. Le 28 décembre 2009, X._ a demandé le bénéfice de l'assistance juridique pour recourir devant le Tribunal administratif du canton de Genève à l'encontre de la décision de la Commission de recours du 1er décembre 2009.
Le Vice-Président du Tribunal de première instance du canton de Genève a refusé cette requête par décision du 6 janvier 2010 au motif que le recours était voué à l'échec. X._ a recouru contre la décision de rejet de sa demande d'assistance juridique auprès de la Cour de justice du canton de Genève, qui, par décision du Vice-Président du 25 mai 2010, a rejeté le recours.
D. Contre la décision du 25 mai 2010, X._ forme un recours constitutionnel subsidiaire au Tribunal fédéral, en concluant à 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 auprès du Tribunal administratif à l'encontre de la décision de la Commission de recours du 1er décembre 2009. A titre subsidiaire, il demande le renvoi du dossier à l'autorité cantonale pour nouvelle décision au sens des considérants. Il requiert par ailleurs l'octroi de l'effet suspensif et le bénéfice de l'assistance judiciaire pour la procédure devant le Tribunal fédéral.
Le Président de la Cour de justice a déclaré s'en rapporter à justice sur la question de l'effet suspensif et a renvoyé à la décision entreprise concernant la violation du droit d'être entendu invoquée. Le Vice-Président du Tribunal de première instance n'a pas formulé d'observations, à l'instar de l'Office cantonal.

Considérant en droit:
1. Le Tribunal fédéral examine d'office et librement sa compétence, respectivement la recevabilité des recours qui lui sont soumis (<ref-law>; <ref-ruling> consid. 1 p. 37).
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>. 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 (<ref-ruling> consid. 4 p. 338; confirmé notamment in arrêt 2D_25/2009 du 25 mai 2009 consid. 1.1).
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 (arrêt 2C_239/2010 du 30 juin 2010 consid. 1.2; cf. <ref-ruling> consid. 2.2). 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 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, a qualité pour recourir (<ref-law>), le recours est en principe recevable, dès lors qu'il porte sur une décision incidente au sens de l'<ref-law> (cf. supra consid. 1.1) émanant d'une autorité judiciaire cantonale supérieure statuant en dernière instance (art. 114 et 86 al. 1 let. d et al. 2 LTF).
2. Le recours constitutionnel subsidiaire ne peut être formé que pour violation des droits constitutionnels (<ref-law>). Le Tribunal fédéral ne se saisit 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; <ref-ruling> consid. 3.2 p. 88; <ref-ruling> consid. 3.2 p. 444).
3. Le recourant se plaint en premier lieu d'une violation de son droit d'être entendu au sens de l'art. 29 al. 2 Cst. et d'une application arbitraire de l'art. 143A al. 3 de la loi genevoise sur l'organisation judiciaire du 22 novembre 1941 (RS/GE E 2 05; ci-après LOJ gen.). Il reproche au Vice-Président de la Cour de justice d'avoir statué sur son recours sans l'entendre oralement au préalable.
3.1 Dès lors que les garanties minimales en matière de droit d'être entendu découlant de l'art. 29 al. 2 Cst. ne comprennent en principe pas le droit d'être entendu oralement (<ref-ruling> consid. 2.1 p. 428; <ref-ruling> consid. 9b p. 219), la question soulevée par le recourant consiste à se demander si le droit cantonal et plus particulièrement l'art. 143A al. 3 LOJ gen. offre une protection plus étendue dont il n'aurait arbitrairement pas pu bénéficier.
A cet égard, il ne faut pas perdre de vue qu'arbitraire et violation du droit ne sauraient être confondus. Selon la jurisprudence, l'arbitraire, prohibé par l'art. 9 Cst., ne résulte pas du seul fait qu'une autre solution pourrait entrer en considération ou même qu'elle serait préférable; le Tribunal fédéral n'annule la décision attaquée que lorsque celle-ci est manifestement insoutenable, qu'elle se trouve en contradiction claire avec la situation de fait, qu'elle viole gravement une norme ou un principe juridique indiscuté, ou encore lorsqu'elle heurte de manière choquante le sentiment de la justice et de l'équité. Pour qu'une décision soit annulée pour cause d'arbitraire, il ne suffit pas que la motivation formulée soit insoutenable, il faut encore que la décision apparaisse arbitraire dans son résultat (<ref-ruling> consid. 1.3 p. 4 s; <ref-ruling> consid. 3.1 p. 265 s.).
3.2 Selon l'art. 143A al. 3 LOJ gen., 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. Après avoir considéré qu'il n'était pas arbitraire d'interpréter cette disposition en ce sens qu'elle n'obligeait pas en tout cas le président de la Cour de justice à entendre le recourant oralement avant de statuer (cf. arrêt 5P.113/1998 du 8 mai 1998 consid. 4a et l'arrêt cité), le Tribunal fédéral a modifié son approche dans un arrêt 4P.195/2002 du 13 novembre 2002. Il a indiqué que l'art. 143A al. 3 LOJ gen. allait plus loin que le droit constitutionnel fédéral en permettant au recourant de faire valoir ses allégués et ses moyens non seulement par écrit, mais aussi oralement. Selon la conception actuelle, l'audition de l'intéressé en vertu de cette disposition est donc la règle et non pas l'exception. Elle ne peut être refusée que dans des circonstances particulières. Par ailleurs, elle ne dépend pas d'une requête expresse du recourant (arrêt précité consid. 2.3, confirmé in arrêts 1P.573/2004 du 2 novembre 2004, in RDAF 2005 I p. 55, consid. 2.2 et 5A_496/2009 du 21 octobre 2009 consid. 2.1).
Dans l'arrêt 4P.195/2002 du 13 novembre 2002, le Tribunal fédéral a ainsi considéré que l'art. 143A al. 3 LOJ gen. avait été interprété de manière arbitraire, car la magistrate intimée n'avait indiqué ni dans sa décision, ni dans ses observations les motifs de refus de l'audition, alors même qu'aucune raison ne paraissait justifier, par exception au principe général, que l'intéressé soit privé de sa faculté de s'exprimer oralement. Dans l'arrêt paru à la RDAF 2005 I p. 55, il a annulé la décision attaquée pour violation du droit d'être entendu parce que l'autorité cantonale, qui n'invoquait aucune circonstance particulière à l'appui de son refus d'audition, ne s'était pas assurée que le recourant n'entendait pas user de son droit de s'exprimer oralement en l'interpellant à ce propos, alors qu'il lui était précisément reproché de n'avoir pas respecté son devoir de participer à l'établissement de certains faits. Enfin, dans l'arrêt 5A_496/2009 rendu le 21 octobre 2009, le Tribunal fédéral a aussi admis une violation du droit d'être entendu du recourant en relevant que la seule affirmation figurant dans la décision attaquée selon laquelle le dossier contenait suffisamment d'éléments pour statuer, qui n'était étayée par aucune considération concrète, ne suffisait pas à justifier une dérogation à l'art. 143A al. 3 LOJ gen. Il a été souligné que l'audition du recourant s'imposait d'autant plus que le juge cantonal avait confirmé le refus de l'assistance judiciaire en invoquant l'absence de succès du recours, ce qui nécessitait une appréciation anticipée et sommaire des faits et des preuves, à propos desquels il avait été admis que le droit d'être entendu du recourant avait été enfreint.
3.3 Dans la décision entreprise du 25 mai 2010, le Vice-Président de la Cour de justice a seulement indiqué qu'il n'y avait pas lieu d'entendre le recourant, parce que celui-ci ne le sollicitait pas et que le dossier contenait tous les éléments utiles pour statuer. Il ressort de la jurisprudence précitée que cette affirmation n'est pas suffisante pour justifier de déroger à l'art. 143A al. 3 2ème phrase LOJ gen., dès lors qu'il appartient à l'autorité d'interpeller le recourant, même sans requête expresse de sa part, pour s'assurer qu'il renonce à faire usage de son droit ou d'expliquer concrètement les éléments à l'appui de sa renonciation à entendre celui-ci.
A cela s'ajoute que l'on ne voit pas ce qui permettait en l'espèce au juge cantonal d'affirmer qu'il disposait des éléments justifiant de ne pas entendre le recourant. Comme dans l'arrêt du 21 octobre 2009 précité, le recourant a fait valoir, à l'appui de sa demande d'assistance juridique, une violation de son droit d'être entendu, reprochant à l'Office cantonal d'avoir prononcé son renvoi sans l'avoir invité à se déterminer sur cette mesure. Or, dans la décision entreprise, le Vice-Président a laissé ouverte la question de savoir si l'Office cantonal n'aurait pas dû entendre formellement le recourant avant de décider de son renvoi, au motif qu'une éventuelle violation du droit d'être entendu avait été réparée devant la Commission de recours. Une telle affirmation n'est toutefois que du ressort de l'instance de recours, le juge chargé de statuer sur l'assistance judiciaire n'intervenant que sous l'angle des chances de succès (cf. <ref-ruling> consid. 5 p. 616; <ref-ruling> consid. 2.3.1 p. 135 s.). Quoi qu'il en soit, la décision attaquée repose sur une appréciation anticipée et sommaire des faits et des preuves à propos desquels le recourant n'a justement pu s'exprimer avant le prononcé du renvoi par l'autorité administrative. Dans un tel contexte et même si l'on ne peut exclure que ce vice ait été réparé par la procédure devant la Commission de recours, il n'est à l'évidence pas possible d'en conclure à l'existence de circonstances particulières propres à entraîner une dérogation à l'art. 143A al. 3 LOJ gen. en l'absence d'indications concrètes dans la décision attaquée. En ne procédant pas à l'audition du recourant ou, à tout le moins, en ne s'assurant pas que celui-ci entendait renoncer à sa prérogative de s'exprimer oralement devant lui en l'interpellant à ce propos, le Vice-Président a manifestement violé l'art. 143A al. 3 LOJ gen.
Compte tenu de la nature formelle de cette garantie, l'admission du grief entraîne l'annulation de la décision attaquée, indépendamment des chances de succès de la requête sur le fond (arrêts précités 5A_496/2009 consid. 2.2 in fine; 1P.573/2004 consid. 2.2 in fine et 4P.195/2002 consid. 2.3 in fine).
4. En conclusion, il convient d'admettre le recours, d'annuler la décision attaquée et de renvoyer la cause à l'autorité cantonale pour qu'elle procède à l'audition du recourant et rende une nouvelle décision (cf. <ref-law>). Il ne sera pas perçu de frais (<ref-law>). En revanche, le canton de Genève versera des dépens au recourant qui obtient gain de cause (art. 68 al. 1 et 2 LTF), ce qui rend sans objet sa requête d'assistance judiciaire dans la présente procédure.
Avec ce prononcé, la demande d'effet suspensif pour la procédure devant le Tribunal fédéral perd aussi tout objet.

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 2'000 francs à titre de dépens.
5. Le présent arrêt est communiqué au mandataire du recourant, au Vice-président de la Cour de justice du canton de Genève, au Vice-président du Tribunal de première instance du canton de Genève et à l'Office cantonal de la population du canton de Genève.
Lausanne, le 8 octobre 2010
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: Le Greffier:
Zünd Chatton