Faits:
A. Le 2 mars 2012, A._ a été interpellé à la suite d'une dénonciation laissant entendre qu'il fomentait le projet de faire tuer le gendarme B._. Il lui est reproché d'avoir promis de l'argent dans ce but au mineur C._, qui a confirmé que l'intéressé lui avait demandé de tuer le gendarme en question. A._ a été prévenu de tentative d'assassinat, subsidiairement de tentative d'instigation à assassinat. Le dénommé D._ a également déclaré que A._ lui avait proposé de l'argent pour frapper un policier, de sorte que la prévention a été étendue à l'instigation à lésions corporelles graves. La police ayant découvert quelque 20'000 fr. dissimulés en divers endroits d'un commerce de A._, celui-ci a également été prévenu de blanchiment d'argent. Il est enfin prévenu d'infraction à la loi fédérale sur les étrangers (LEtr; RS 142.20) pour avoir employé sept personnes illégalement entre 2009 et 2012.
B. Le Tribunal des mesures de contrainte du canton de Genève (ci-après: le Tmc) a ordonné la détention provisoire de A._. Cette détention a été prolongée à plusieurs reprises et le Tmc a rejeté des requêtes de mise en liberté provisoire. La Cour de céans a confirmé une décision de prolongation de la détention, en constatant l'existence de charges suffisantes et celle d'un risque de collusion (arrêt 1B_393/2012 du 24 juillet 2012).
Par ordonnance du 12 septembre 2012, le Tmc a ordonné une nouvelle prolongation de la détention jusqu'au 12 novembre 2012, en retenant l'existence de risques de fuite, de collusion et de réitération. Statuant sur recours de l'intéressé, la Chambre pénale de recours de la Cour de justice du canton de Genève (ci-après: la Cour de justice) a confirmé cette décision par arrêt du 10 octobre 2012. Elle a retenu en substance que les charges étaient suffisantes, que le risque de récidive était bien réalisé et que le principe de la proportionnalité était respecté. Elle a en revanche estimé que le risque de collusion ne pouvait plus être retenu. Par ordonnance du 14 novembre 2012, le Tmc a ordonné une nouvelle prolongation de la détention jusqu'au 21 décembre 2012, en retenant les risques de fuite et de réitération et en relevant que cette prolongation devrait suffire pour clore l'instruction et renvoyer le prévenu en jugement.
C. Agissant par la voie du recours en matière pénale, A._ demande au Tribunal fédéral d'annuler l'arrêt de la Cour de justice et d'ordonner sa mise en liberté immédiate, subsidiairement de prononcer des mesures de substitution, en particulier le paiement d'une caution de 25'000 francs. Il requiert en outre l'octroi de l'assistance judiciaire. La Cour de justice a renoncé à se déterminer. Le Ministère public a présenté des observations, concluant au rejet du recours. Le recourant a formulé des 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. La détention du recourant ne se fonde plus sur l'ordonnance du 12 septembre 2012, mais sur l'ordonnance du 14 novembre 2012 prolongeant la détention jusqu'au 21 décembre 2012. Cette dernière ordonnance repose toutefois sur les mêmes motifs de détention que ceux retenus dans l'arrêt attaqué, auquel elle renvoie largement, de sorte que le recourant conserve un intérêt actuel et pratique à l'examen de ses griefs (<ref-law>). 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>).
3. Le recourant ne présente pas de grief contre le caractère suffisant des charges, mais il conteste notamment l'existence d'un risque de réitération. Il se plaint dans ce cadre d'une violation de son droit d'être entendu.
3.1 Aux termes de l'art. 221 al. 1 let. c CPP, la détention provisoire peut être ordonnée lorsqu'il y a sérieusement lieu de craindre que le prévenu "compromette sérieusement la sécurité d'autrui par des crimes ou des délits graves après avoir déjà commis des infractions du même genre". Selon la jurisprudence, il convient de faire preuve de retenue dans l'appréciation du risque de récidive: le maintien en détention ne peut se justifier pour ce motif que si le pronostic est très défavorable et si les délits dont l'autorité redoute la réitération sont graves (<ref-ruling> consid. 4.5 p. 21; <ref-ruling> consid. 2.3 p. 73; <ref-ruling> consid. 2.2 p. 276 et les arrêts cités). Bien qu'une application littérale de l'art. 221 al. 1 let. c CPP suppose l'existence d'antécédents, le risque de réitération peut être également admis dans des cas particuliers alors qu'il n'existe qu'un antécédent, voire aucun dans les cas les plus graves. La prévention du risque de récidive doit en effet permettre de faire prévaloir l'intérêt à la sécurité publique sur la liberté personnelle du prévenu (<ref-ruling> consid. 3-4 p. 18 ss; cf. arrêt 1B_133/2011 du 12 avril 2011 consid. 4.7). Le risque de récidive peut également se fonder sur les infractions faisant l'objet de la procédure pénale en cours, si le prévenu est fortement soupçonné - avec une probabilité confinant à la certitude - de les avoir commises (<ref-ruling> consid. 3.2 p. 86 et les références citées).
3.2 En l'occurrence, la Cour de justice relève que le recourant a été condamné en 2007 pour avoir menacé un fonctionnaire de l'inspection cantonale du commerce, qu'il était dès lors de longue date en délicatesse avec les autorités dans l'exploitation de son commerce et que cet antécédent, combiné aux projets avortés faisant l'objet de la présente procédure, renforçait le soupçon que l'intéressé était déterminé à se venger des contrôles répétés de son établissement. L'autorité précédente mentionne en outre une plainte pénale déposée contre le recourant par une ancienne amie pour des menaces de mort. Elle retient enfin une gradation dans les intentions du recourant, qui a commencé par des menaces verbales pour en arriver à des projets d'agression, voire d'élimination physique.
Les éléments retenus par la Cour de justice pour étayer le risque de récidive ne sont guère étoffés. En effet, le seul véritable antécédent consiste en une condamnation datant de 2007 pour menace contre un fonctionnaire, à qui le recourant avait dit "je vous conseille de prendre une assurance vie". Comme le reconnaît la Cour de justice, cet antécédent révèle davantage un risque d'insoumission aux prescriptions de la police du commerce qu'un danger de passage à l'acte contre la vie ou l'intégrité corporelle. De plus, l'arrêt attaqué n'expose pas les motifs qui permettraient de considérer les infractions faisant l'objet de la présente procédure comme établies "avec une probabilité confinant à la certitude" au sens de la jurisprudence susmentionnée. Compte tenu de la gravité des accusations portées contre le recourant, une certaine prudence s'impose néanmoins dans l'examen du risque de récidive, l'intérêt à la sécurité publique revêtant dans un tel cas un caractère prépondérant.
Dans ces conditions, la plainte de l'ex-amie du recourant mentionnée dans l'arrêt attaqué peut être pertinente pour apprécier le risque de récidive, puisqu'elle avait apparemment pour objet des menaces de mort. Cet élément pourrait le cas échéant apporter un éclairage sur le caractère du recourant et sur sa propension à proférer de telles menaces, voire étayer le raisonnement de la Cour de justice quant à une gradation dans les comportements de l'intéressé. Cela étant, la plainte précitée est un élément de fait nouveau, qui n'est mentionnée ni dans l'ordonnance du Tmc du 12 septembre 2012, ni dans la demande de prolongation du Ministère public du 4 septembre 2012, ni dans le précédent arrêt de la Cour de justice du 31 mai 2012 auquel renvoient les autorités précitées. Le recourant n'a donc pas pu s'exprimer sur la portée de la plainte en question dans le cadre de l'examen du risque de récidive. C'est dès lors à juste titre qu'il invoque à cet égard une violation de son droit d'être entendu, qui comprend notamment le droit pour l'intéressé de s'exprimer sur les éléments pertinents avant qu'une décision ne soit prise touchant sa situation juridique (<ref-ruling> consid. 3.2 p. 272; <ref-ruling> consid. 5.1 p. 293; <ref-ruling> consid. 3.2 p. 494 et les références). Cette violation ne peut pas être guérie devant la Cour de céans, qui ne dispose pas du même pouvoir d'examen que l'autorité précédente (art. 97 et 105 LTF; cf. <ref-ruling> consid. 2.2 p. 204; <ref-ruling> consid. 5.1 p. 390 et les références). Le recours doit donc être admis pour ce motif et la cause renvoyée à la Cour de justice pour qu'elle rende une nouvelle décision à brève échéance, après avoir donné au recourant l'occasion de se déterminer au sujet des faits issus de la plainte pénale en question. Cette question demeure d'actualité, la nouvelle ordonnance de prolongation de la détention du 14 novembre 2012 se limitant à renvoyer à l'arrêt attaqué en ce qui concerne le risque de récidive.
4. L'admission du recours pour ce motif formel n'a pas pour conséquence la mise en liberté immédiate du recourant (cf. <ref-ruling> consid. 3b p. 64; <ref-ruling> consid. 5g p. 308; <ref-ruling> consid. 5d p. 93). Le caractère suffisant des charges pesant sur l'intéressé n'est en effet pas valablement contesté et il n'est pas exclu que le maintien en détention soit justifié par un risque de récidive. La demande de mise en liberté doit donc être rejetée.
5. Il s'ensuit que le recours doit être admis partiellement et l'arrêt attaqué annulé. La cause est renvoyée à la Cour de justice pour pour qu'elle rende, à brève échéance, une nouvelle décision prise dans le respect du droit d'être entendu du recourant. La demande de mise en liberté est rejetée. Il n'y a pas lieu de percevoir de frais judiciaires (<ref-law>). Le recourant obtenant partiellement gain de cause, l'Etat de Genève versera un indemnité à titre de dépens à son conseil (<ref-law>). Vu l'issue du recours, la demande d'assistance judiciaire est sans objet.

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est partiellement admis. L'arrêt attaqué est annulé et la cause est renvoyée à la Cour de justice du canton de Genève, Chambre pénale de recours, pour nouvelle décision dans le sens des considérants.
2. La demande de mise en liberté immédiate est rejetée.
3. Il n'est pas perçu de frais judiciaires.
4. L'Etat de Genève versera au conseil du recourant une indemnité de 2'000 fr. à titre de dépens.
5. 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 30 novembre 2012
Au nom de la Ire Cour de droit public
du Tribunal fédéral suisse
Le Président: Fonjallaz
Le Greffier: Rittener