Faits: A. Le 2 mars 2012, A._ a été interpellé à la suite d'une dénonciation laissant entendre qu'il fomentait le projet de faire tuer le gendarme B._. Il lui est reproché d'avoir promis environ 5'000 fr. au mineur C._ pour éliminer ce gendarme, qui avait régulièrement contrôlé ses deux commerces et qui l'avait pris en flagrant délit d'emploi "au noir" et de vente illégale de boissons alcooliques à emporter. C._ a confirmé que A._ lui avait demandé par deux fois de tuer le gendarme en question. A._ a été prévenu de tentative d'assassinat, subsidiairement de tentative d'instigation à assassinat. Le dénommé D._ a également déclaré que A._ lui avait proposé 5'000 ou 6'000 fr. pour frapper un policier, de sorte que la prévention a été étendue à l'instigation à lésions corporelles graves. La police ayant découvert quelque 20'000 fr. dissimulés en divers endroits d'un commerce de A._, celui-ci a également été prévenu de blanchiment d'argent. Il est enfin prévenu d'infraction à la loi fédérale sur les étrangers (LEtr; RS 142.20) pour avoir employé sept personnes illégalement entre 2009 et 2012. B. Le Tribunal des mesures de contrainte du canton de Genève (ci-après: le Tmc) a ordonné la détention provisoire de A._ jusqu'au 16 avril 2012. Cette détention a été prolongée par la suite, le Tmc ayant en outre rejeté deux requêtes de mise en liberté provisoire. Par ordonnance du 8 mai 2012, le Tmc a prolongé une nouvelle fois la détention du prénommé jusqu'au 8 juillet 2012, en retenant l'existence de risques de collusion et de réitération. Statuant sur recours de l'intéressé, la Chambre pénale de recours de la Cour de justice du canton de Genève (ci-après: la Cour de justice) a confirmé cette décision par arrêt du 31 mai 2012. Elle a retenu en substance que les charges étaient suffisantes, que les risques précités étaient bien réalisés et que le principe de la proportionnalité était respecté. Par ordonnance du 10 juillet 2012, le Tmc a ordonné une nouvelle prolongation de la détention jusqu'au 10 septembre 2012, pour les même motifs. C. Agissant par la voie du recours en matière pénale, A._ demande au Tribunal fédéral d'annuler l'arrêt de la Cour de justice et d'ordonner sa mise en liberté immédiate. La Cour de justice a renoncé à se déterminer. Le Ministère public a présenté des observations, concluant au rejet du recours. Le recourant a formulé des observations complémentaires.