Faits: A. Le 13 mai 2012, A._ a été arrêté à l'aéroport de Genève, après la découverte dans ses bagages d'une vingtaine de cartes de crédit "skimmées". Ce ressortissant de Malaisie a expliqué en substance avoir été envoyé en Suisse pour faire des achats avec les cartes en question. Deux compatriotes du prénommé ont été arrêtés en même temps que lui pour les mêmes motifs. Le Ministère public du canton de Genève (ci-après: le Ministère public) a mis A._ en prévention d'utilisation frauduleuse d'un ordinateur et de tentative d'escroquerie. Par ordonnance du 15 mai 2012, le Tribunal des mesures de contrainte du canton de Genève (ci-après: le Tmc) a ordonné sa détention provisoire jusqu'au 15 août 2012, en raison de risques de collusion et de fuite. 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 1er juin 2012. Elle a retenu 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é. Le même jour, le Ministère public a ordonné la mise en liberté immédiate de A._. B. 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 de constater le caractère illicite de la détention ainsi qu'une violation de l'art. 29 al. 1 Cst. et des art. 5 et 6 CEDH. Il requiert en outre l'octroi de l'assistance judiciaire. La Cour de justice s'est déterminée sommairement en se référant à sa décision. Le Ministère public conclut au rejet du recours. Le recourant a présenté des observations complémentaires.