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. 