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.