Faits:
A. Le 25 juin 2011, X._ a été découvert ensanglanté et fortement alcoolisé dans l'allée d'un immeuble à Genève. Entendu quelques heures plus tard par la police, il a affirmé avoir été blessé par balles et a porté plainte contre inconnu. Le Ministère public du canton de Genève (ci-après: le Ministère public) a ouvert une enquête, qui a révélé de nombreuses incohérences entre les déclarations du prénommé et les constats médicaux-légaux. En réalité, il apparaissait que l'intéressé s'était blessé en enjambant une barrière. X._ s'est finalement excusé pour avoir prétendu s'être fait tirer dessus. Le 3 août 2011, le Ministère public a rendu une ordonnance de non-entrée en matière et condamné le plaignant aux frais de procédure, arrêtés à 1'733,15 fr., en application de l'art. 427 al. 2 du code de procédure pénale suisse (CPP; RS 312.0).
B. X._ a recouru contre cette ordonnance auprès de la Chambre pénale de recours de la Cour de justice du canton de Genève (ci-après: la Cour de justice). Il alléguait en substance qu'il avait fait ses premières déclarations dans un état de grande confusion, qu'il était encore alcoolisé et qu'il ne se souvenait de rien, de sorte qu'il ne se justifiait pas de mettre à sa charge les frais inhérents aux importantes mesures d'instruction ordonnées sans délai. Il demandait en outre l'octroi de l'assistance judiciaire. Par arrêt du 27 septembre 2011, la Cour de justice a admis ce recours dans la mesure de sa recevabilité, en relevant que les frais de procédure devaient être laissés à la charge de l'Etat, l'ordonnance de non-entrée en matière étant confirmée pour le surplus.
La Cour de justice a statué sur la requête d'assistance judiciaire par ordonnance séparée du 3 octobre 2011. Elle a considéré que la requête n'avait plus d'objet en ce qui concerne l'exonération des frais au sens de l'art. 136 al. 2 let. b CPP et qu'elle devait être rejetée s'agissant de la désignation d'un conseil juridique gratuit, celle-ci n'étant pas nécessaire pour la défense des intérêts du plaignant au sens de l'art. 136 al. 2 let. c CPP.
C. Agissant par la voie du recours en matière pénale, X._ demande au Tribunal fédéral d'annuler cette ordonnance et de renvoyer la cause à l'instance précédente pour qu'elle lui accorde l'assistance judiciaire pour la procédure de recours cantonale. Il requiert en outre l'octroi de l'assistance judiciaire devant le Tribunal fédéral. Le Ministère public et la Cour de justice ont renoncé à se déterminer.

Considérant en droit:
1. Le Tribunal fédéral examine d'office et librement la recevabilité des recours qui lui sont soumis (<ref-ruling> consid. 1 p. 43; <ref-ruling> consid. 1 p. 331 et les arrêts cités).
1.1 Conformément à l'art. 78 LTF, une décision relative à la défense d'office dans une cause pénale peut faire l'objet d'un recours en matière pénale.
1.2 Aux termes de l'art. 81 al. 1 let. b ch. 5 LTF, la partie plaignante qui a participé à la procédure de dernière instance cantonale est habilitée à recourir au Tribunal fédéral si la décision attaquée peut avoir des effets sur le jugement de ses prétentions civiles. Le recourant n'ayant pas formulé de telles prétentions, il ne peut pas se prévaloir de la qualité pour agir sur la base de cette disposition.
Cela étant, la jurisprudence admet que le plaignant qui n'a pas la qualité pour recourir sur le fond peut invoquer la violation de droits que la loi de procédure applicable ou le droit constitutionnel lui reconnaît comme partie à la procédure, lorsque cette violation équivaut à un déni de justice formel (<ref-ruling> consid. 1.4 p. 44, 29 consid. 1.9 p. 40; <ref-ruling> consid. 2.3.2 p. 232 s. et les références citées). Il en va notamment ainsi du droit à l'assistance judiciaire (cf. arrêt 1B_436/2011 du 21 septembre 2011 consid. 1). Ce droit étant reconnu à la partie plaignante aux conditions de l'art. 136 CPP, celle-ci est recevable à se plaindre du fait que l'assistance judiciaire lui a été refusée.
1.3 La décision attaquée, qui rejette définitivement la requête litigieuse alors que la procédure au fond s'est achevée, revêt un caractère final (art. 90 LTF). Pour le surplus, le recours est formé en temps utile (art. 100 al. 1 LTF) contre une décision rendue en dernière instance cantonale (art. 80 LTF) et les conclusions présentées sont recevables au regard de l'art. 107 al. 2 LTF. Il y a donc lieu d'entrer en matière.
2. Le recourant soutient en substance que la Cour de justice a violé les art. 136 al. 2 let. c CPP et 29 al. 3 Cst. en refusant de lui désigner un conseil juridique gratuit.
2.1 Il se prévaut en premier lieu de l'art. 136 al. 2 let. c CPP, qui prévoit que l'assistance judiciaire comprend la désignation d'un conseil juridique gratuit. Le recourant admet cependant que les conditions d'application de cette disposition ne sont manifestement pas réalisées en l'espèce, dans la mesure où l'assistance requise ne visait pas à faire valoir des prétentions civiles au sens de l'art. 136 al. 1 CPP. En effet, conformément à cette disposition, l'assistance judiciaire n'est octroyée à la partie plaignante que « pour lui permettre de faire valoir ses prétentions civiles » et uniquement si « l'action civile ne paraît pas vouée à l'échec ». Le législateur a sciemment limité l'octroi de l'assistance judiciaire aux cas où le plaignant peut faire valoir des prétentions civiles. Il a ainsi tenu compte du fait que le monopole de la justice répressive est par principe exercé par l'Etat, de sorte que l'assistance judiciaire de la partie plaignante se justifie en priorité pour faire valoir ses conclusions civiles (cf. Message du 21 décembre 2005 relatif à l'unification du droit de la procédure pénale, FF 2006 1160). Dans la mesure où le recourant ne fait pas valoir de telles prétentions, il ne peut pas fonder sa requête sur l'art. 136 CPP.
2.2 Le recourant invoque également l'art. 29 al. 3 Cst., sans toutefois démontrer que cette disposition constitutionnelle lui octroie une protection plus large que l'art. 136 al. 2 let. c CPP. Il apparaît au contraire que les normes en question ont une portée identique en ce qui concerne les griefs soulevés. Le recourant fonde en effet son argumentation sur le caractère nécessaire de l'intervention d'un conseil juridique; il affirme en substance que la sauvegarde de ses droits exigeait l'assistance d'un avocat, la cause présentant des difficultés juridiques particulières qu'il ne pouvait pas surmonter seul. Or, ces critères déduits de l'art. 29 al. 3 Cst. s'appliquent également à l'art. 136 al. 2 let. c CPP, qui a repris la condition de la norme constitutionnelle en question (cf. Message du 21 décembre 2005 précité, FF 2006 1160; GORAN MAZZUCCHELLI/MARIO POSTIZZI, in Basler Kommentar StPO, 2011, n. 17 ss ad art. 136; MAURICE HARARI/CORINNE CORMINBOEUF, in Commentaire romand CPP, 2011, n. 60 ss ad art. 136). Par conséquent, l'art. 29 al. 3 Cst. n'accorde pas sur ce point une protection plus étendue que l'art. 136 al. 2 let. c CPP. C'est en outre à juste titre que le recourant n'invoque pas l'art. 6 par. 3 let. c CEDH, cette norme n'étant applicable qu'à l'accusé.
2.3 En définitive, les griefs du recourant relatifs au caractère nécessaire de l'intervention d'un conseil juridique ne peuvent être examinés qu'à l'aune de l'art. 136 al. 2 let. c CPP. Or, le recourant ne peut pas prétendre à l'assistance judiciaire gratuite sur cette base, faute de prétentions civiles. L'arrêt attaqué doit donc être confirmé par substitution de motifs, sans qu'il soit nécessaire d'examiner si le critère de l'art. 136 al. 2 let. c CPP a été correctement appliqué.
3. Il s'ensuit que le recours doit être rejeté. Dès lors que le recourant est dans le besoin et que l'on peut admettre que ses conclusions n'étaient pas d'emblée vouées à l'échec, l'assistance judiciaire doit lui être accordée pour la procédure de recours devant le Tribunal fédéral (art. 64 al. 1 LTF). Il y a lieu de désigner Me Jacques Emery en qualité d'avocat d'office et de fixer d'office ses honoraires, qui seront supportés par la caisse du Tribunal fédéral (art. 64 al. 2 LTF). Le recourant est en outre dispensé des frais judiciaires (art. 64 al. 1 LTF).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté.
2. La demande d'assistance judiciaire est admise. Me Jacques Emery est désigné comme défenseur d'office du recourant et ses honoraires, supportés par la caisse du Tribunal fédéral, sont fixés à 1'500 francs.
3. Il n'est pas perçu de frais judiciaires.
4. Le présent arrêt est communiqué au mandataire du recourant, au Ministère public et à la Cour de justice du canton de Genève, Cham-bre pénale de recours.
Lausanne, le 31 mai 2012
Au nom de la Ire Cour de droit public
du Tribunal fédéral suisse
Le Président: Fonjallaz
Le Greffier: Rittener