Faits:
A. Le 24 juin 2012, A._ a été arrêté à la suite d'une bagarre impliquant plusieurs individus. Il lui est reproché d'avoir asséné des coups de machette au dénommé B._, dont le pronostic vital se serait trouvé engagé. Le Ministère public du canton de Genève (ci-après: le Ministère public) l'a prévenu de tentative de meurtre, d'agression, voire de rixe, ainsi que d'infraction à la loi fédérale sur les étrangers. A._ a été placé en détention provisoire par le Tribunal des mesures de contrainte du canton de Genève (ci-après: le Tmc).
Par ordonnance du 6 août 2012, le Tmc a rejeté une demande de mise en liberté provisoire déposée le 25 juillet 2012 par A._. Il a considéré que les charges étaient suffisantes, qu'il existait des risques de fuite et de collusion et qu'aucune mesure de substitution n'entrait en considération. A._ 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), qui a rejeté ce recours par arrêt du 3 septembre 2012. Relevant que les charges étaient suffisantes, la Cour de justice a estimé qu'il existait des risques concrets de fuite et de collusion. Aucune mesure de substitution n'étant à même de pallier efficacement ces risques, elle a considéré que le maintien en détention provisoire était justifié.
B. Par recours du 3 octobre 2012, A._ demande au Tribunal fédéral d'annuler cet arrêt, d'ordonner sa libération immédiate et de prononcer toute mesure de substitution jugée utile. Il requiert en outre l'octroi de l'assistance judiciaire. Le Ministère public conclut au rejet du recours. Le Tribunal cantonal a renoncé à se déterminer. Le recourant a présenté de brèves observations complémentaires.

Considérant en droit:
1. Selon l'<ref-law>, le recours en matière pénale est ouvert contre les décisions rendues en matière pénale, dont font partie les décisions relatives à la détention provisoire ou pour des motifs de sûreté au sens des <ref-law> (<ref-ruling> consid. 1 p. 23). 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. Une mesure de détention préventive 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 art. 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. A l'appui de ses griefs, le recourant présente de nombreux faits qui ne ressortent pas de l'arrêt attaqué. Il perd ainsi de vue que, conformément à l'<ref-law>, le Tribunal fédéral statue en principe sur la base des faits établis par l'autorité précédente. L'<ref-law> ne permet de s'en écarter que si les faits ont été établis de façon manifestement inexacte - notion qui correspond à celle d'arbitraire au sens de l'art. 9 Cst. (<ref-ruling> consid. 4.1.2 p. 62; <ref-ruling> consid. 2.4 p. 314; <ref-ruling> consid. 4.3 p. 62) - ou en violation du droit au sens de l'<ref-law>. Le recourant peut critiquer les constatations de fait aux même conditions, si la correction du vice soulevé est susceptible d'influer sur le sort de la cause (<ref-law>). Il lui appartient de démontrer que ces conditions sont réalisées, par une argumentation répondant aux exigences de motivation de l'<ref-law> (cf. <ref-ruling> consid. 1.4.3 p. 254 s.). Une telle démonstration faisant clairement défaut en l'espèce et une constatation inexacte des faits n'étant pas d'emblée évidente, il n'y a pas lieu de s'écarter des faits retenus dans l'arrêt attaqué. Les allégués de fait qui ne ressortent pas de celui-ci sont dès lors irrecevables.
4. Dans un premier grief, le recourant conteste le caractère suffisant des charges.
4.1 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. Il n'appartient cependant pas au juge de la détention de procéder à une pesée complète des éléments à charge et à décharge et d'apprécier la crédibilité des personnes qui mettent en cause le prévenu. Il doit uniquement examiner s'il existe des indices sérieux de culpabilité justifiant une telle mesure. 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. 3.2 p. 126 s.; <ref-ruling> consid. 3c p. 146).
4.2 En l'espèce, la Cour de justice a retenu que le recourant avait à tout le moins accepté de causer des blessures sérieuses à B._, dès lors qu'il s'était muni d'une machette comportant une lame d'environ 25 cm en vue de le rencontrer. Il avait en outre fait usage de cette arme contre le prénommé, dont le pronostic vital s'était trouvé engagé. C'était en vain que l'intéressé invoquait un état de légitime défense, de défense excusable ou des faits justificatifs; ces éléments n'apparaissaient pas réalisés et relevaient du juge du fond. Il résultait en revanche clairement de la procédure que le recourant avait porté un ou deux coups de machette à B._, qui n'était pas armé. La découverte à proximité des lieux de la bagarre d'un couteau portant les empreintes du recourant constituait en outre un indice de la volonté de celui-ci de s'armer avant de rencontrer la victime.
Le recourant ne remet pas en cause cette appréciation de façon convaincante. Se fondant pour l'essentiel sur des allégués de fait irrecevables (cf. supra consid. 3), il tente de faire porter à B._ la responsabilité de la bagarre qui a éclaté, en rapportant en substance que le prénommé et un comparse avaient "enlevé" une prostituée logeant chez le recourant. Les multiples allégations relatives à cet événement sont sans pertinence pour apprécier les actes reprochés au recourant. Ceux-ci ont en effet eu lieu dans un deuxième temps, après que B._ et son comparse eurent déposé la prostituée en question à un poste de police. Lorsque les protagonistes se sont retrouvés, le recourant était armé et s'était fait accompagner de deux autres individus. Le déroulement exact de l'altercation et les agissements des uns et des autres n'ont pas à être établis précisément à ce stade de l'enquête. Il en va de même des raisons qui ont motivé l'acte du recourant et de la question de savoir si la vie de la victime a été concrètement mise en danger. La Cour de justice relève d'ailleurs que les conclusions de l'institut de médecine légale sont attendues sur ce dernier point. Quoi qu'il en soit, il n'appartient pas au juge de la détention de trancher ces questions, puisqu'il doit uniquement examiner s'il existe des indices sérieux de culpabilité. Or, il est établi que le recourant s'était armé d'une machette pour rencontrer B._ et qu'il a frappé ce dernier avec cette arme, ce qu'il reconnaît. Il existe donc des indices d'une volonté du recourant de causer des blessures sérieuses au prénommé, à tout le moins d'une acceptation de ce risque. Il est également établi que la victime a été blessée au cours d'une altercation qui a toutes les apparences d'une rixe, délit réprimé par l'<ref-law>. C'est dès lors à juste titre que la Cour de justice a constaté l'existence de charges suffisantes, de sorte que ce grief doit être rejeté.
5. Le recourant conteste également l'existence des risques motivant son maintien en détention, notamment le risque de fuite.
5.1 Le risque de fuite 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'État 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; <ref-ruling> consid. 4a p. 70; <ref-ruling> consid. 3 p. 67). Il est sans importance que l'extradition du prévenu puisse être obtenue (<ref-ruling> consid. 3d p. 36 s.).
5.2 La Cour de justice relève que le recourant est de nationalité roumaine, qu'il vit en Suisse sans autorisation et qu'il conserve des attaches en Roumanie, où vit notamment sa mère. Compte tenu de la peine encourue s'il devait être reconnu coupable des infractions qui lui sont reprochées, le risque existe qu'il prenne la fuite pour se soustraire à sa condamnation. Pour contester cette appréciation, le recourant se borne à alléguer qu'il a l'intention d'exploiter un restaurant en Suisse, qu'il y vit avec sa compagne depuis plusieurs années et qu'il a déposé une demande d'autorisation de séjour. La Cour de justice a déjà répondu à ces arguments, en relevant que les chances d'obtenir un permis de séjour sont sérieusement compromises, de même que le vague projet d'exploiter légalement un restaurant. Dans ces conditions, la seule présence de sa compagne en Suisse n'apparaît pas suffisante pour dissuader le recourant de prendre la fuite ou de disparaître dans la clandestinité pour échapper à une éventuelle condamnation. Le maintien en détention étant justifié par le risque précité, il n'y a pas lieu d'examiner s'il peut également être motivé par un risque de collusion, comme le retient l'arrêt attaqué.
5.3 Le recourant propose encore des mesures de substitution prévues par l'<ref-law>, à savoir la saisie de documents d'identité et le versement d'une caution de 20'000 fr. financée par sa famille. Le dépôt des documents d'identité du recourant est clairement insuffisant pour pallier le risque de fuite, cette mesure n'empêchant pas l'intéressé de passer la frontière ou de disparaître dans la clandestinité. S'agissant de la caution, on ne peut que constater avec la Cour de justice que l'origine de la somme proposée demeure complètement indéterminée. Or, le caractère approprié de la garantie offerte doit être apprécié notamment au regard des relations personnelles et financières du prévenu avec les personnes appelées à servir de cautions, afin de déterminer si la perspective de perte du cautionnement agira sur lui comme un frein suffisant pour éviter toute velléité de fuite (<ref-ruling> consid. 4a p. 187, citant l'arrêt CourEDH Neumeister c. Autriche du 27 juin 1968, Série A, vol. 7, § 14; cf. arrêts 1P.165/2006 du 19 avril 2006 consid. 3.2.1, publié in SJ 2006 I p. 395, 1P.690/2004 du 14 décembre 2004 consid. 2.4.3 et les références). Il convient également de faire preuve de prudence quant à l'origine des fonds proposés comme sûretés (cf. arrêt 1P.570/2003 du 20 octobre 2003 et les références, arrêt CourEDH Punzelt c. République tchèque du 25 avril 2000, § 85 ss). En l'absence de tout renseignement sur les personnes appelées à servir de caution et sur l'origine des fonds proposés, il n'est pas possible d'apprécier la garantie offerte. Pour le surplus, la Cour de justice a considéré que les autres mesures de substitution n'entraient pas en considération, ce qui n'est pas contesté par le recourant. On ne voit au demeurant pas quelle autre mesure pourrait atteindre le même but que la détention, dont la durée respecte en outre le principe de la proportionnalité.
6. Il s'ensuit que le recours doit être rejeté, dans la mesure de sa recevabilité. Dès lors que l'on peut encore admettre que le recourant est dans le besoin et que ses conclusions n'étaient pas d'emblée vouées à l'échec, l'assistance judiciaire doit lui être accordée (<ref-law>). Il y a lieu de désigner Me Philippe Currat 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 (<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é dans la mesure où il est recevable.
2. La demande d'assistance judiciaire est admise. Me Philippe Currat 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, Chambre pénale de recours.
Lausanne, le 19 octobre 2012
Au nom de la Ire Cour de droit public
du Tribunal fédéral suisse
Le Juge présidant: Aemisegger
Le Greffier: Rittener