Faits:
A. A._, ressortissant jamaïcain, se trouve en détention provisoire depuis le 4 mai 2011, sous la prévention de viol aggravé de concert avec un tiers. Sa détention provisoire a été régulièrement prolongée par le Tribunal des mesures de contrainte du canton de Genève, en dernier lieu pour une durée de trois mois jusqu'au 22 novembre 2011, par ordonnance du 22 août 2011.
Par arrêt du 13 septembre 2011, la Chambre pénale de recours de la Cour de justice du canton de Genève (ci-après: la Cour de justice) a rejeté le recours formé par l'intéressé contre cette ordonnance. Elle a considéré en substance que les charges étaient suffisantes, qu'il existait des risques de récidive, de fuite et de collusion que les mesures de substitution proposées n'étaient pas à même de pallier.
B. Dans le cadre d'une procédure en cours devant le Tribunal correctionnel du canton de Genève pour tentative de meurtre (procédure P/17808/2009), A._ avait été mis en liberté provisoire, moyennant le versement d'une caution de 9'100 francs et le dépôt de son passeport. L'audience de jugement dans cette cause, agendée aux 9 et 10 mai 2011, a été reportée en raison de la présente affaire.
Il existe encore une autre procédure pénale ouverte contre le prénommé pour viol, en cours d'instruction au Ministère public du canton de Genève (procédure P/19147/2008).
C. Agissant par la voie du recours en matière pénale, A._ demande principalement au Tribunal fédéral d'annuler l'arrêt du 13 septembre 2011 et d'ordonner sa mise en liberté immédiate. Il requiert subsidiairement d'ordonner des mesures de substitution en vertu de l'art. 237 du code de procédure pénale suisse (CPP; RS 312.0). Il sollicite également l'assistance judiciaire.
La Cour de justice et le Ministère public du canton de Genève ont renoncé à se déterminer.

Considérant en droit:
1. Le recours en matière pénale (<ref-law>) est en principe ouvert contre une décision relative au maintien en détention provisoire au sens des <ref-law>. Dès lors que l'acte de procédure litigieux ne met pas un terme à la procédure pénale (art. 90 s. LTF), il s'agit d'une décision incidente prise séparément au sens de l'<ref-law>. La décision ordonnant la prolongation de la détention provisoire du prévenu étant susceptible de lui causer un préjudice irréparable au sens de l'<ref-law>, elle peut faire l'objet d'un recours au Tribunal fédéral. Selon l'art. 81 al. 1 let. a et let. b ch. 1 LTF, l'accusé a qualité pour agir. Pour le surplus, le recours est formé en temps utile (<ref-law>) contre une décision rendue en dernière instance cantonale (<ref-law>) et les conclusions présentées sont recevables au regard de l'<ref-law>.
2. Dans un grief d'ordre formel qu'il convient d'examiner en premier lieu, le recourant reproche à la Cour de justice d'avoir violé son droit d'être entendu, en motivant insuffisamment l'arrêt attaqué.
2.1 Le droit d'être entendu garanti à l'art. 29 al. 2 Cst. implique notamment pour l'autorité l'obligation de motiver sa décision. Selon la jurisprudence, la motivation d'une décision est suffisante lorsque l'autorité mentionne, au moins brièvement, les motifs qui l'ont guidée et sur lesquels elle a fondé sa décision, de manière à ce que l'intéressé puisse se rendre compte de la portée de celle-ci et l'attaquer en connaissance de cause. L'autorité ne doit toutefois pas se prononcer sur tous les moyens des parties; elle peut se limiter aux questions décisives (<ref-ruling> consid. 4.1 p. 88 et les arrêts cités).
Selon la jurisprudence rendue en matière de prolongation de la détention provisoire, on admet qu'une motivation par renvoi à de précédentes décisions ou par adhésion aux motifs de la demande de prolongation de la détention peut être acceptable, pour autant que le prévenu ne fasse pas valoir d'arguments nouveaux. Encore faut-il que les motifs auxquels il est renvoyé soient développés de manière suffisante au regard des exigences de l'art. 29 al. 2 Cst. (<ref-ruling> consid. 4c p. 285; <ref-ruling> consid. 3a p. 409).
2.2 Dans l'arrêt attaqué, la Cour de justice s'est référée, en partie, à ses arrêts des 26 juillet 2011 et 17 [recte 16] août 2011. Elle a expliqué avoir procédé de la sorte puisque les griefs étaient formulés en des termes quasi identiques lors de l'instance précédente. Elle a précisé encore que le dossier n'avait pas connu, depuis, la moindre évolution vers un affaiblissement des charges, tout en exposant les nouveaux éléments versés au dossier depuis la reddition de son arrêt précédent.
A la lecture de l'arrêt entrepris et des deux arrêts auxquels il renvoie, on comprend parfaitement sur quelles bases la Cour de justice s'est appuyée pour considérer que les indices de culpabilité étaient suffisants (cf. infra consid. 3.3), que le risque de fuite était réalisé et les mesures de substitution proposées insuffisantes (cf. infra consid. 4.2 et 4.4). De plus, l'instance précédente a motivé le risque de collusion par le fait qu'un témoin avait affirmé avoir subi des pressions. Elle n'a pas non plus exclu le danger de récidive, au motif que le recourant était aussi cité à comparaître pour tentative de meurtre et également poursuivi pour viol dans une troisième procédure. La Cour cantonale a exposé de façon certes brève, mais satisfaisante du point de vue du droit d'être entendu, les motifs qui ont emporté sa conviction. Dans la mesure où le recourant critique la pertinence de ces motifs, il soulève une question de fond qui sera examinée ci-après. Mal fondé, le grief doit être rejeté.
3. Sur le fond, le recourant ne met pas en cause la base légale de sa détention. Il conteste en revanche l'existence de forts soupçons à son encontre.
3.1 Une mesure de détention provisoire n'est compatible avec la liberté personnelle (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'<ref-law>. 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. art. 221 al. 1 let. a, b et c CPP). Préalablement à ces conditions, il doit exister à l'égard de l'intéressé des charges suffisantes, soit de sérieux soupçons de culpabilité (<ref-law>; art. 5 par. 1 let. c CEDH; arrêt 1B_63/2007 du 11 mai 2007 consid. 3 non publié in <ref-ruling>). Le Tribunal fédéral examine librement ces questions, sous réserve toutefois de l'appréciation des faits, revue sous l'angle restreint des art. 97 al. 1 et 105 al. 2 LTF (<ref-ruling> consid. 2.5 p. 73 s. et les références).
3.2 Pour qu'une personne soit placée en détention préventive, il doit exister à son égard des charges suffisantes ou des indices sérieux de culpabilité, c'est-à-dire des raisons plausibles de la soupçonner d'avoir commis une infraction. L'intensité des charges propres à motiver un maintien en détention préventive n'est pas la même aux divers stades de l'instruction pénale; si des soupçons, même encore peu précis, peuvent être suffisants dans les premiers temps de l'enquête, la perspective d'une condamnation doit apparaître vraisemblable après l'accomplissement des actes d'instruction envisageables (<ref-ruling> consid. 3c p. 146 et les références citées).
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 é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 (<ref-ruling> consid. 3c p. 146).
3.3 En l'occurrence, le recourant avance qu'aucun des témoins n'a indiqué qu'il avait eu des relations sexuelles avec la victime, pas même celle-ci. A cet égard, la Cour de justice a toutefois précisé que B._, entendu par la police, avait déclaré que tant le prévenu que son comparse lui avaient dit immédiatement après être sortis de la chambre avoir eu des relations sexuelles consenties avec la victime et qu'ils lui auraient par la suite précisé ne pas avoir violé cette jeune femme; B._ avait confirmé ses propos devant le Procureur le 3 août 2011, mais au prix de nombreuses tergiversations.
S'ajoutaient à cela les déclarations de C._ - notamment sur le fait qu'elle avait été empêchée de se rendre dans la pièce où la victime était seule avec les prévenus -, la chronologie de leurs sorties successives de cette pièce et la déposition de D._ pour qui des relations sexuelles avaient bien eu lieu. De plus, E._, chauffeur de taxi, avait déclaré que la victime et son amie n'avaient pas d'emblée envie de descendre du taxi en bas de l'immeuble où s'étaient déroulés les faits incriminés et avaient été extirpées de son taxi par les "garçons"; plus tard, lorsqu'il était revenu chercher l'un d'eux devant le même immeuble, trois des quatre personnes présentes lui avaient demandé où était le poste de police le plus proche et s'il était prêt à témoigner qu'ils n'avaient pas forcé les filles à sortir du taxi une heure et demie ou deux heures plus tôt; il avait encore, dans les jours suivants, reçu un téléphone de l'un des prévenus lui demandant à nouveau s'il était prêt à témoigner dans le sens précité. A l'instar de la Cour de justice, on discerne mal, si ce n'est pour chercher à couvrir une activité que l'on veut taire, la raison de telles interventions.
Le recourant affirme également qu'aucun des rapports médicaux n'atteste que les lésions à la vulve auraient été commises par lui et qu'aucune trace de son ADN n'a été trouvée sur la victime selon le rapport établi par le Centre universitaire romand de médecine légale (CURML) le 10 juin 2011. Le dernier rapport du CURML, daté du 28 juillet 2011, indique seulement la présence de deux traces d'ADN masculines - dont il est très probable qu'elles proviennent des deux prévenus - sur le poignet gauche de la victime. Sur ce point, la Cour de justice a retenu que cela permettait toutefois d'envisager sérieusement que le re courant avait tenu la victime, ce qui fondait le soupçon, à supposer qu'il n'ait pas entretenu de relations sexuelles avec elle, d'une probable coactivité.
Dans ces conditions, on peut admettre, à l'instar de la Cour de justice, qu'il existe, au stade actuel de l'enquête, un faisceau d'indices suffisant pour justifier un maintien en détention du recourant, étant rappelé que c'est au juge du fond et non à celui de la détention qu'il incombera d'apprécier la culpabilité de l'intéressé ainsi que la valeur probante des différentes déclarations.
4. Le recourant conteste également l'existence de risques de fuite, de récidive et de collusion. Si de tels risques devaient toutefois être retenus, il requiert la mise en oeuvre de mesures de substitution au sens de l'<ref-law>, telles que l'assignation à résidence, le port d'un bracelet électronique, l'obligation de se rendre au poste de police de manière régulière et l'interdiction de s'entretenir avec les personnes en lien avec l'affaire.
4.1 Selon la jurisprudence, le risque de fuite au sens de l'<ref-law> doit s'analyser en fonction d'un ensemble de critères tels que le caractère de l'intéressé, sa moralité, ses ressources, ses liens avec l'Etat qui le poursuit ainsi que ses contacts à l'étranger, qui font apparaître le risque de fuite non seulement possible, mais également probable (<ref-ruling> consid. 4a p. 70 et la jurisprudence citée). La gravité de l'infraction ne peut pas, à elle seule, justifier la prolongation de la détention, même si elle permet souvent de présumer un danger de fuite en raison de l'importance de la peine dont le prévenu est menacé (<ref-ruling> consid. 3a p. 62, 117 Ia 69 consid. 4a p. 70, 108 Ia 64 consid. 3 p. 67).
4.2 En l'occurrence, il est vrai que le recourant peut se prévaloir de liens avec la Suisse, dans la mesure où sa mère et ses deux enfants y résident. Cela étant, ses deux enfants vivent avec leurs mères respectives et, à l'instar de l'instance précédente, il y a lieu de constater que le recourant ne fait pas valoir, et démontre encore moins, qu'il fournit des prestations pour leur entretien et qu'il s'occupe effectivement d'eux. De plus, l'intéressé est ressortissant de la Jamaïque - où vit son père -, n'exerce aucun emploi en Suisse et n'a fourni aucune indication concernant ses moyens de subsistance.
Les attaches du recourant avec la Suisse doivent de surcroît être mises en balance avec la gravité des actes qui lui sont reprochés et la peine privative de liberté encourue, qui pourrait l'inciter à faire certains sacrifices pour y échapper. L'ensemble de ces éléments apparaît suffisant pour retenir un risque concret de fuite.
Face à ces arguments, le recourant se borne à relever qu'il n'a jamais quitté le territoire suisse et qu'il s'est présenté à tous les actes de procédure, même lorsqu'il risquait d'être condamné dans le cadre de la procédure lui valant d'être cité pour tentative de meurtre, "dont la peine prononcée pourrait être aussi importante voire plus que celle de la [présente cause]". Cette argumentation est toutefois insuffisante à faire admettre l'invraisemblance du risque de fuite et tend plutôt à montrer que le recourant, inculpé d'une infraction passible d'une peine privative de liberté importante, doublée d'une citation à comparaître pour une autre infraction passible d'une lourde peine, possède de sérieuses raisons de ne pas rester en Suisse. Dans ces circonstances, c'est à juste titre que la Cour de justice a retenu un risque concret de fuite.
4.3 L'affirmation d'un risque de fuite dispense d'examiner s'il existe aussi un danger de collusion et de récidive, au sens de l'art. 221 al. 1 let. b et let. c CPP.
4.4 Conformément au principe de la proportionnalité (art. 36 al. 3 Cst.), il convient d'examiner les possibilités de mettre en oeuvre d'autres solutions moins dommageables que la détention (règle de la nécessité). Cette exigence est concrétisée par l'<ref-law>, qui prévoit que le tribunal compétent ordonne une ou plusieurs mesures moins sévères en lieu et place de la détention si ces mesures permettent d'atteindre le même but que la détention. Selon l'<ref-law>, font notamment partie des mesures de substitution la saisie des documents d'identité (let. b), l'assignation à résidence ou l'interdiction de se rendre dans un certain lieu ou un certain immeuble (let. c), l'obligation de se présenter régulièrement à un service administratif (let. d) et l'interdiction d'entretenir des relations avec certaines personnes (let. g).
En l'espèce, les mesures de substitution susceptibles de pallier les risques de fuite proposées par le recourant, notamment l'assignation à résidence, apparaissent clairement insuffisantes au regard de l'intensité desdits risques. De plus, l'obligation de se présenter régulièrement au poste de police n'est pas de nature à empêcher une personne dans la situation du recourant de s'enfuir à l'étranger, mais permet uniquement de constater la fuite, quelques jours après sa survenance.
Quant à la caution, comme l'a retenu l'instance précédente, si l'on peut concevoir que le montant déposé dans la procédure pour tentative de meurtre était important pour une seule infraction, il ne l'est plus lorsque l'on se trouve en présence de trois procédures, qui engendrent la possibilité d'une peine autrement plus lourde.
Par ailleurs, il y a lieu de relever que la surveillance électronique préconisée par le recourant ne constitue pas en soi une mesure de substitution mais uniquement un moyen de contrôler l'exécution d'une telle mesure, en particulier une assignation à résidence (cf. arrêt 1B_447/2011 du 21 septembre 2011 consid. 3.4). S'il apparaît, comme en l'espèce, que cette dernière mesure n'est pas apte à prévenir le risque de fuite, la surveillance électronique, dépourvue en soi d'effet préventif, ne saurait être mise en oeuvre.
En outre, le strict respect de l'interdiction d'entretenir des relations avec toute personne en lien avec l'affaire est difficilement vérifiable et une violation de celle-ci est susceptible d'avoir des conséquences irréparables sur la manifestation de la vérité.
5. Il s'ensuit que le recours doit être rejeté. Dès lors que le recourant est dans le besoin et que ses conclusions ne paraissaient pas d'emblée vouées à l'échec, l'assistance judiciaire doit lui être accordée (<ref-law>). Le recourant requiert la désignation de Me Garance Stackelberg en qualité d'avocate d'office. Il y a lieu de faire droit à cette requête et de fixer d'office les honoraires de l'avocate, qui seront supportés par la caisse du Tribunal fédéral (<ref-law>). Le recourant est en outre dispensé des frais judiciaires (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté.
2. La demande d'assistance judiciaire est admise. Me Garance Stackelberg est désignée comme avocate 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é à la mandataire du recourant, au Ministère public et à la Chambre pénale de recours de la Cour de justice du canton de Genève.
Lausanne, le 8 novembre 2011
Au nom de la Ire Cour de droit public
du Tribunal fédéral suisse
Le Président: Fonjallaz
La Greffière: Tornay Schaller