Faits: A. X._ a été inculpé le 19 février 2009 de complicité de tentative d'assassinat pour avoir, en septembre ou octobre 2007, procuré, en toute connaissance de cause, un pistolet à A._, qui avait été mandaté pour assassiner B._. Le 5 octobre 2007, A._ avait tiré, au moyen de cette arme, un coup de feu sur sa victime qu'il avait blessée de façon à mettre sa vie en danger. L'inculpation de X._ repose sur une dénonciation de C._, avec lequel il a partagé la même cellule à la prison de D._ pendant la période du 26 novembre 2008 au 21 janvier 2009. Par courrier du 29 janvier 2009, C._ a fait savoir au Procureur général qu'il était en possession d'informations concernant X._, selon lesquelles ce dernier lui avait confié avoir fait partie d'un groupe qui avait projeté de tuer une personne pour une histoire de vengeance; son rôle avait été de fournir l'arme utilisée lors des faits et le véhicule qui devait servir à la fuite des participants. C._ a confirmé ses déclarations devant la police et le juge d'instruction les 6 février, 27 février et 17 mars 2009. B. Par ordonnance du 22 mai 2009, la Chambre d'accusation du canton de Genève (ci-après: la Chambre d'accusation) a refusé la mise en liberté provisoire du prévenu, considérant que des charges suffisantes existaient à son égard. Par ailleurs, le risque de collusion apparaissait particulièrement concret et intense, le risque de récidive devait également être retenu et le danger de fuite ne pouvait être exclu. C. Agissant par la voie du recours en matière pénale, X._ demande au Tribunal fédéral d'annuler l'ordonnance de la Chambre d'accusation du 22 mai 2009 et de prononcer sa mise en liberté immédiate. Subsidiairement il conclut à sa mise en liberté immédiate moyennant le dépôt de toutes pièces d'identité auprès du Procureur général du canton de Genève. Il requiert en outre l'assistance judiciaire. La Chambre d'accusation se réfère aux considérants de sa décision. Le Ministère public du canton de Genève conclut au rejet du recours dans la mesure où il est recevable.