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.

Considérant en droit:
1. Les décisions relatives au maintien en détention préventive sont des décisions en matière pénale au sens de l'art. 78 al. 1 LTF (cf. <ref-ruling> consid. 1.1 p. 273). Formé en temps utile (art. 100 al. 1 LTF) contre une décision prise en dernière instance cantonale (art. 80 LTF) et qui touche le recourant dans ses intérêts juridiquement protégés (art. 81 al. 1 let. a et b ch. 1 LTF), le recours en matière pénale est recevable.
2. Une mesure de détention préventive n'est compatible avec la liberté personnelle, garantie par les art. 10 al. 2 Cst. et 5 CEDH, que si elle repose sur une base légale (art. 31 al. 1 et 36 al. 1 Cst.), soit en l'espèce l'art. 34 du code de procédure pénale genevois (CPP/GE; cf. également l'art. 27 Cst./GE). Elle doit en outre correspondre à un intérêt public et respecter le principe de la proportionnalité (art. 36 al. 2 et 3 Cst.; <ref-ruling> consid. 2c p. 270). Pour que tel soit le cas, la privation de liberté doit être justifiée par les besoins de l'instruction, un risque de fuite ou un danger de collusion ou de réitération (cf. 34 let. a à c CPP/GE). La gravité de l'infraction - et l'importance de la peine encourue - n'est, à elle seule, pas suffisante (<ref-ruling> consid. 3a p. 62; <ref-ruling> consid. 4a p. 70). Préalablement à ces conditions, il doit exister à l'égard de l'intéressé des charges suffisantes, soit de sérieux soupçons de culpabilité (art. 5 par. 1 let. c CEDH; arrêt 1B_63/2007 du 11 mai 2007 consid. 3 non publié in <ref-ruling>; art. 34 in initio CPP/GE). S'agissant d'une restriction grave à la liberté personnelle, le Tribunal fédéral examine librement ces questions, sous réserve toutefois de l'appréciation des preuves, revue sous l'angle restreint de l'arbitraire (<ref-ruling> consid. 2d p. 271; pour une définition de l'arbitraire, cf. art. 9 Cst. et <ref-ruling> consid. 3.1 p. 153; <ref-ruling> consid. 5.1 p. 17; <ref-ruling> consid. 2.1 p. 219; <ref-ruling> consid. 2.1 p. 9). L'autorité cantonale dispose ainsi d'une grande liberté dans l'appréciation des faits (<ref-ruling> consid. 3; <ref-ruling> consid. 3b).
3. Le recourant conteste l'existence de charges suffisantes: son inculpation repose uniquement sur les déclarations de C._, dont la valeur probante est nulle. Les motifs de C._ seraient en effet égoïstes et intéressés, son but étant principalement de convaincre le Procureur général de sa "transformation" en prison et de son désir, en tant que bon citoyen, d'aider la justice en dénonçant son compagnon de cellule. De plus, les rapports des intéressés étaient tendus, voire franchement mauvais, tout au long de leur séjour dans la même cellule. A cela s'ajoute le problème de la langue, le recourant parlant mal le français et C._ ayant admis qu'il était difficile de le comprendre. Il est probable que C._ a mal compris les explications du recourant, lequel a appris l'existence de l'arme emballée dans un chiffon lors d'une audition devant le juge d'instruction le 9 janvier 2009, ou qu'il a utilisé les faits en modifiant légèrement le contexte, pour s'en servir dans sa lettre de dénonciation. Finalement, les déclarations de C._ comportent plusieurs incohérences. Celui-ci a affirmé que le recourant ne s'était jamais confié à lui pendant qu'une troisième personne se trouvait dans la même cellule; or, dès le 2 décembre 2008, soit six jours après l'arrivée du recourant, il y avait pratiquement en permanence un troisième détenu dans leur cellule.
3.1 Appelé à se prononcer sur la constitutionnalité d'une décision de maintien en détention préventive, le Tribunal fédéral n'a pas à procéder à une pesée complète des éléments à charge et à décharge, ni à apprécier la crédibilité des personnes ou des éléments de preuve mettant en cause le prévenu. Il doit uniquement examiner s'il existe des indices sérieux de culpabilité justifiant une telle mesure (arrêt 1P.405/1998 du 30 novembre 1998 consid. 7b/cc, non publié in <ref-ruling>; <ref-ruling> consid. 3c p. 146). L'intensité des charges permettant de justifier une mesure de détention n'est pas la même aux divers stades de l'instruction pénale; si l'on admet qu'après l'accomplissement des actes d'instruction envisageables la perspective d'une condamnation doive apparaître vraisemblable, des soupçons, même encore peu précis, peuvent être considérés comme suffisants dans les premiers temps de l'enquête (arrêt 1P.713/1991 du 27 novembre 1991 consid. 4b/aa).
3.2 En l'espèce, la Chambre d'accusation a retenu que plusieurs éléments ressortant des déclarations de C._ s'étaient révélés exacts, que celui-ci pouvait avoir eu connaissance de certains faits par des co-détenus ou des rumeurs circulant à la prison, mais que certains points précis concernant le mécanicien chargé de réparer le véhicule et la présence du chiffon emballant l'arme, ne semblaient pouvoir être parvenus à sa connaissance que par des confidences de son co-détenu. Par ailleurs, certains éléments étaient inconnus de tous, y compris des personnes impliquées dans le cadre de la procédure, puisqu'à l'époque où auraient eu lieu ces confidences, les parties n'avaient pas accès à certaines pièces du dossier. La manière dont C._ avait expliqué les différentes étapes des révélations de son co-détenu apparaissait crédible et cohérente et il ressortait du dossier que le recourant "se débrouillait" en français et que les deux comparses avaient également utilisé des gestes pour se comprendre. S'agissant des tensions entre les intéressés, le recourant soutenait qu'il s'était battu avec son co-détenu et qu'il avait demandé à plusieurs reprises de changer de cellule; ses dires n'étaient toutefois pas confirmés par les renseignements transmis le 23 avril 2009 par le directeur de la prison de D._.
Au vu des circonstances précitées, la Chambre d'accusation pouvait effectivement estimer que les déclarations précises et répétées de C._ apparaissaient crédibles. Les doutes du recourant quant aux motifs qui ont poussé son ancien co-détenu à le dénoncer sont de simples suppositions qui ne permettent pas d'emblée de conclure à un mensonge créé de toutes pièces; d'ailleurs, lors de son audience de jugement, C._ n'a aucunement fait état de sa collaboration dans la présente procédure, dans le but d'améliorer sa situation pénale. De même, le fait qu'un troisième détenu était "pratiquement en permanence" dans la cellule n'est pas a priori de nature à exclure toute confidence de la part du recourant. Il apparaît ainsi que l'ensemble des éléments retenus dans l'ordonnance attaquée constitue un faisceau d'indices suffisant pour justifier un maintien en détention, étant rappelé que c'est au juge du fond et non à celui de la détention qu'il incombera d'apprécier la valeur probante des différentes déclarations.
4. Le recourant conteste l'existence d'un risque de récidive. Il fait valoir que les mauvais antécédents retenus par la Chambre d'accusation ne s'apparentent pas aux faits de la cause, puisqu'il s'agissait, pour la plupart des cas, de petits larcins.
Selon la jurisprudence, le maintien en détention préventive n'est admissible que si le pronostic de récidive est très défavorable et si les délits à craindre sont de nature grave. La simple possibilité, hypothétique, de commission de nouvelles infractions de même nature, ou la vraisemblance que soient commises des infractions mineures, sont des motifs insuffisants (<ref-ruling> consid. 2.2 p. 276; <ref-ruling> consid. 3a p. 62). En l'occurrence, la Chambre d'accusation se contente de relever que le recourant a été condamné à six reprises depuis 2006, sans indiquer de quelles infractions il s'agissait. Ceci est manifestement insuffisant pour fonder un risque de récidive, surtout si, comme l'affirme le recourant et comme cela semble ressortir du dossier, les condamnations précédentes concernaient des infractions d'ordre mineur contre le patrimoine. Dans ces conditions, la Chambre d'accusation a mésusé de son pouvoir d'appréciation en admettant qu'il existait un risque concret de récidive. Le recours doit ainsi être admis sur ce point.
5. Le recourant conteste également l'existence d'un risque de collusion et de fuite.
5.1 Le maintien du prévenu en détention peut être justifié par l'intérêt public lié aux besoins de l'instruction en cours. Tel est le cas par exemple lorsqu'il est à craindre que l'intéressé ne mette sa liberté à profit pour faire disparaître ou altérer les preuves, ou pour prendre contact avec des témoins ou d'autres prévenus, afin de tenter d'influencer leurs déclarations (<ref-ruling> consid. 3.2 p. 23; <ref-ruling> consid. 2.1 p. 151 et les arrêts cités). On ne saurait toutefois se contenter d'un risque de collusion abstrait, car ce risque est inhérent à toute procédure pénale en cours et doit, pour permettre à lui seul le maintien en détention préventive, présenter une certaine vraisemblance. L'autorité doit ainsi indiquer, au moins dans les grandes lignes et sous réserve des opérations à conserver secrètes, quels actes d'instruction elle doit encore effectuer et en quoi la libération du prévenu en compromettrait l'accomplissement (<ref-ruling> consid. 3.2 p. 23; <ref-ruling> consid. 2.1 p. 151 et les arrêts cités).
Par ailleurs, selon la jurisprudence, le risque de fuite doit s'analyser en fonction d'un ensemble de critères tels que la gravité de l'infraction, le caractère de l'intéressé, sa moralité, ses ressources, ses liens avec l'État qui le poursuit ainsi que ses contacts à l'étranger, qui font apparaître un tel danger non seulement possible, mais également probable (<ref-ruling> consid. 3a p. 62 et les arrêts cités). Lorsqu'elle admet l'existence d'un risque de fuite, l'autorité doit en outre examiner s'il ne peut être contenu par une mesure moins rigoureuse (<ref-ruling> consid. 3a p. 62; <ref-ruling> consid. 2c p. 271; <ref-ruling> consid. 3 p. 67; <ref-ruling> consid. 2a p. 381/382 et les arrêts cités).
5.2 Dans le cas particulier, la Chambre d'accusation a considéré que le risque de fuite ne pouvait être exclu, vu la gravité des faits reprochés au recourant et la peine à laquelle il s'exposait. Or, la gravité de l'infraction ne peut pas, à elle seule, justifier la prolongation de la détention, de sorte qu'il convient d'examiner s'il existe d'autres indices d'un éventuel risque de fuite. L'ordonnance attaquée est toutefois muette sur ces questions: on ignore notamment le statut du recourant en Suisse, sa situation personnelle et financière, son intégration ainsi que ses attaches familiales et ses liens avec l'étranger. Il apparaît ainsi que les éléments indispensables pour apprécier le risque de fuite font défaut, de sorte que le Tribunal fédéral n'est pas en mesure de statuer.
Il en est de même s'agissant du risque de collusion. La Cour cantonale indique que ce danger apparaît particulièrement concret et intense dans une procédure qui a fait l'objet d'une mesure de super-suspension prolongée à plusieurs reprises où règne la loi du silence et où les inculpés, notamment le recourant, tentent de s'entretenir ensemble pendant les audiences. Il ressort effectivement du dossier que, lors de l'audience du 8 mai 2009, la Juge d'instruction a dû intervenir pour empêcher le recourant de s'entretenir avec un autre inculpé et qu'elle a dû plusieurs fois lui dire de se taire. C'est toutefois le seul élément concret sur lequel la Chambre d'accusation fonde un risque de collusion; elle n'indique pas en quoi la libération de l'intéressé compromettrait l'accomplissement des actes d'instruction encore à effectuer. Au demeurant, comme l'allègue le recourant, d'autres inculpés ont été libérés, l'autorité ayant considéré que pour ceux-ci, le risque de collusion n'existait plus. Il aurait dès lors été nécessaire de motiver plus précisément pourquoi ce risque ne pouvait pas être écarté chez le recourant. Il n'appartient pas au Tribunal fédéral de rechercher dans le dossier les éléments qui permettraient de justifier le maintien en détention sous cet angle.
Il y a dès lors lieu de constater que la décision attaquée ne contient pas "les motifs déterminants de fait et de droit" requis par l'art. 112 al. 1 let. b LTF, si bien qu'elle doit être annulée sur ce point et que la cause doit être renvoyée à l'autorité cantonale en application de l'art. 112 al. 3 LTF.
6. Il s'ensuit que le recours doit être partiellement admis. La décision attaquée est annulée et la cause est renvoyée à l'instance précédente pour qu'elle rende, à brève échéance, conformément au principe de célérité, une décision qui réponde aux réquisits de l'art. 112 al. 1 LTF. Il n'y a pas lieu de percevoir des frais judiciaires (art. 66 al. 4 LTF). Le recourant, assisté d'un avocat, a droit à des dépens, à la charge de l'Etat de Genève (art. 68 al. 1 LTF). Dans ces conditions, sa demande d'assistance judiciaire est sans objet.

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est partiellement admis. La décision attaquée est annulée et la cause est renvoyée à la Présidente de la Chambre d'accusation de la Cour de justice du canton de Genève pour nouvelle décision dans le sens des considérants.
2. Il n'est pas perçu de frais judiciaires.
3. Une indemnité de 1'500 fr. est allouée à X._ à titre de dépens, à la charge de l'Etat de Genève.
4. Le présent arrêt est communiqué aux parties et à la Cour de justice du canton de Genève, Chambre d'accusation.
Lausanne, le 10 juillet 2009
Au nom de la Ire Cour de droit public
du Tribunal fédéral suisse
Le Président: La Greffière:
Féraud Mabillard