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. 