Faits:
A. A._ a été arrêté le 25 juin 2012 dans le cadre d'une enquête conduite par le Ministère public du canton de Neuchâtel, Parquet général (ci-après: le Ministère public), et portant sur des infractions contre l'intégrité sexuelle (art. 187 à 190 CP) commises sur la fille de sa compagne. Par ordonnance du 28 juin 2012, le Tribunal des mesures de contrainte des Montagnes et du Val-de-Ruz (ci-après: le Tmc) a ordonné la détention provisoire du prénommé jusqu'au 28 août 2012, au motif qu'il existait des charges suffisantes ainsi qu'un risque de collusion.
B. Le 21 août 2012, le Ministère public a requis la prolongation de la détention provisoire du prénommé, en mentionnant des éléments nouveaux recueillis le 20 août 2012 par la police judiciaire et qui seraient de nature à confirmer les déclarations de la victime. Le lendemain, le Tmc a invité A._ à se déterminer et il a ordonné la prolongation temporaire de la détention en application de l'art. 227 al. 4 du Code de procédure pénale suisse (CPP; RS 312.0). A._ s'est déterminé par l'intermédiaire de son mandataire le 27 août 2012. Le prénommé a en outre formé lui-même une demande de mise en liberté, parvenue au Tmc le 29 août 2012. Le jour même, le Tmc a transmis cette requête au Ministère public comme objet de sa compétence et il lui a communiqué les déterminations de A._. Le Tmc impartissait en outre au Ministère public un délai de trois jours pour produire un bref rapport de police relatif aux éléments nouveaux mentionnés dans sa requête. Le 5 septembre 2012, le Ministère public a pris position sur la demande de mise en liberté et il s'est déterminé sur les éléments requis par le Tmc. Le 6 septembre 2012, le Tmc a invité A._ à se déterminer sur la prise de position et les observations du Ministère public "dans les plus brefs délais, au plus tard dans les trois jours".
C. Le 5 septembre 2012, A._ a déposé un recours pour déni de justice ou retard injustifié auprès de l'Autorité de recours en matière pénale du Tribunal cantonal du canton de Neuchâtel (ci-après: le Tribunal cantonal). Cette autorité a rejeté le recours par arrêt du 14 septembre 2012, considérant en substance que le délai de cinq jours de l'<ref-law> ne courrait qu'à partir de la réception du dernier acte des parties. Elle relevait en outre que le Tmc avait procédé à une instruction consciencieuse et diligente du dossier en sollicitant des informations complémentaires, de sorte qu'il n'y avait ni déni de justice, ni retard injustifié.
D. Agissant par la voie du recours en matière pénale, A._ demande au Tribunal fédéral de constater une violation de l'<ref-law> et du principe de célérité, de réformer l'arrêt attaqué et de dire que les frais de seconde instance cantonale sont laissés à la charge de l'Etat. Il conclut subsidiairement à l'annulation de l'arrêt attaqué et au renvoi de la cause à l'instance précédente pour nouvelle décision. Il requiert en outre l'octroi de l'assistance judiciaire. Le Tribunal cantonal, le Tmc et le Ministère public ont renoncé à se déterminer.

Considérant en droit:
1. Rendue en matière pénale, la décision querellée peut faire l'objet d'un recours en matière pénale selon l'<ref-law>. L'arrêt attaqué est une décision incidente, qui ne met pas fin à la procédure. Une telle décision ne peut faire l'objet d'un recours au Tribunal fédéral qu'aux conditions de l'art. 93 al. 1 let. a et b LTF. L'hypothèse de la lettre b n'entre pas en considération en l'espèce et il est douteux que la décision querellée cause au recourant un préjudice irréparable au sens de la lettre a. Cependant, en cas de violation du principe de célérité en matière de détention, on admet que le prévenu détenu a droit à obtenir à brève échéance une décision de constatation de cette violation, donnant lieu à une dispense des frais de justice et à une indemnisation pour les frais de défense, cette décision pouvant faire l'objet d'un recours immédiat (arrêt 1B_134/2012 du 8 mai 2012 consid. 1.3; cf. <ref-ruling> consid. 1.3 p. 276 s.). 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>. Il y a donc lieu d'entrer en matière.
2. Invoquant le principe de la célérité, le recourant se plaint du non- respect du délai de cinq jours de l'<ref-law>.
2.1 L'<ref-law> règle la procédure conduite par le Tmc en cas de demande de prolongation de la détention provisoire. Selon l'aliéna 3, le Tmc impartit au détenu un délai de trois jours pour s'exprimer sur la demande de prolongation de la détention déposée par le Ministère public. L'alinéa 4 permet au Tmc d'ordonner une prolongation de la détention provisoire jusqu'à ce qu'il ait statué. Aux termes de l'alinéa 5, le Tmc statue au plus tard dans les cinq jours qui suivent la réception de la réplique ou l'expiration du délai fixé à l'alinéa 3.
2.2 En l'occurrence, le Tmc a d'abord donné au recourant l'occasion de se déterminer sur la demande de prolongation de la détention formulée par le Ministère public, ce que le mandataire du recourant a fait en date du 27 août 2012. Le recourant a toutefois présenté lui-même une demande de mise en liberté, parvenue au Tmc le 29 août 2012. Au regard du principe d'économie de procédure, il se justifiait de trancher simultanément la demande de prolongation de la détention et la demande de mise en liberté. Dès lors que le traitement de celle-ci était dans un premier temps de la compétence du Ministère public - qui pouvait soit l'accepter, soit la renvoyer dans les trois jours au Tmc assortie d'une prise de position défavorable (<ref-law>) - le Tmc ne pouvait pas statuer immédiatement sur la demande de prolongation. Il a dès lors correctement agi en profitant de la transmission de la demande de libération au Ministère public pour demander à ce dernier des renseignements complémentaires. Cette démarche n'a en effet pas prolongé inutilement la procédure, puisque le délai imparti équivalait au délai de trois jours de l'<ref-law>. De même, la prise de position négative du Ministère public devait être transmise au prévenu pour détermination dans les trois jours (<ref-law>), de sorte que le délai équivalant imparti au recourant pour se déterminer sur les observations relatives à la prolongation de la détention n'a pas rallongé la procédure. C'est dès lors en vain que le recourant reproche au Tmc de n'avoir pas statué sur la demande de prolongation le 3 septembre 2012 déjà. Une telle solution aurait en effet contraint le Tmc à traiter séparément les deux requêtes précitées, sans pour autant permettre au recourant d'être fixé plus tôt sur le sort de sa demande de mise en liberté (cf. <ref-law>).
En définitive, le dépôt d'une demande de mise en liberté au cours de la procédure de prolongation de la détention provisoire a créé une situation particulière empêchant la stricte application du délai de l'<ref-law>. Le traitement simultané des deux requêtes conduit en effet à appliquer l'<ref-law>, dont le recourant n'invoque pas la violation. Il n'y a donc en l'espèce aucune violation du principe de célérité susceptible de remettre en cause la légalité de la détention, de sorte que l'arrêt attaqué peut être confirmé, en partie par substitution de motifs.
3. Il s'ensuit que le recours doit être rejeté. Dès lors 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 Alexis Bolle 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é.
2. La demande d'assistance judiciaire est admise. Me Alexis Bolle 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 Tribunal des mesures de contrainte des Montagnes et du Val-de-Ruz, au Ministère public et au Tribunal cantonal du canton de Neuchâtel, Autorité de recours en matière pénale.
Lausanne, le 21 novembre 2012
Au nom de la Ire Cour de droit public
du Tribunal fédéral suisse
Le Président: Fonjallaz
Le Greffier: Rittener