Faits:
A. M._, ressortissante de la République démocratique du Congo, née en 1989, est entrée illégalement en Suisse en février 2002, afin d'y rejoindre K._, née S._ en 1975, titulaire d'un permis de séjour. Dans le cadre d'une procédure de regroupement familial, ont été produits un jugement supplétif du Tribunal de Grande Instance de Kinshasa-Matete du 12 janvier 2002 attestant de la naissance et de l'enregistrement de M._ en tant que fille de S._, ainsi qu'un acte de naissance de M._ délivré par les autorités congolaises le 2 avril 2002.
Présentant un retard scolaire et intellectuel important, M._ a sollicité par l'intermédiaire de son curateur, le 17 mai 2005, des prestations de l'assurance-invalidité sous la forme de subsides pour une formation scolaire spéciale et une formation professionnelle initiale.
Par décision du 20 mars 2006, l'Office de l'assurance-invalidité du canton de Neuchâtel (l'office AI) a refusé de prendre en charge une formation scolaire spéciale au motif que l'atteinte à la santé préexistait à l'entrée en Suisse.
En ce qui concerne le droit à une formation professionnelle initiale, l'office AI a imparti à K._ un délai échéant le 31 août 2006, par lettre du 7 juillet 2006, pour lui transmettre les rapports des analyses génétiques humaines (profils d'ADN) établissant le lien de la filiation maternelle, en précisant que ces tests lui avaient déjà été réclamés par le Service des étrangers. A défaut, l'office AI a informé la prénommée que la prestation requise serait refusée. L'office AI a réitéré ses exigences, le 26 juillet 2006, en faisant savoir à K._ qu'il considérerait que les conditions légales mises à l'octroi des prestations (<ref-law>) ne seraient pas réunies et qu'il rendrait une décision de refus, si les profils d'ADN n'étaient pas en sa possession le 31 août 2006. L'intéressée ne s'est pas manifestée et n'a pas donné suite à cette requête. Par décision du 16 octobre 2006 notifiée à K._ ainsi qu'au curateur de M._ et au Centre X._, l'office AI a nié le droit de M._ à une formation professionnelle initiale; il a précisé que cette décision était rendue en l'état du dossier, en raison du refus de K._ de collaborer.
B. Agissant par son curateur, M._ a déféré la décision du 16 octobre 2006 au Tribunal administratif du canton de Neuchâtel en concluant à son annulation, notamment dans la mesure où elle portait sur la mise en oeuvre d'une expertise ADN dont les frais auraient dû être assumés par K._, détentrice de l'autorité parentale.
L'office AI a conclu au rejet du recours. Contestant la réalité du lien de filiation maternelle, il a requis la production des dossiers du Service des migrations concernant M._ et K._, ainsi que l'audition de la prénommée.
Par jugement du 18 juillet 2007, la juridiction cantonale a constaté l'existence du lien de filiation, reconnaissant en conséquence que M._ remplissait la condition de la durée minimale de cotisations. Elle a dès lors admis le recours et annulé la décision administrative du 16 octobre 2006, puis renvoyé la cause à l'office AI afin qu'il examinât si les conditions du droit à une formation professionnelle initiale étaient remplies et rendît une nouvelle décision.
C. L'office AI interjette un recours en matière de droit public contre ce jugement dont il demande l'annulation.
M._ conclut implicitement au rejet du recours par l'intermédiaire de Me Jean Oesch, avocat à La Chaux-de-Fonds, lequel a été nommé en qualité de curateur ad hoc pour la présente procédure par l'Autorité tutélaire du district de La Chaux-de-Fonds (décision du 18 octobre 2007). Elle sollicite le bénéfice de l'assistance judiciaire pour la procédure fédérale.
L'intimée est désormais mariée et fait l'objet d'une interdiction volontaire (FO du canton de Neuchâtel n°_).
L'Office fédéral des assurances sociales a renoncé à se déterminer.

Considérant en droit:
1. 1.1 Suivant l'<ref-law>, les ressortissants étrangers âgés de moins de 20 ans qui ont leur domicile et leur résidence habituelle (<ref-law>) en Suisse ont droit aux mesures de réadaptation s'ils remplissent eux-mêmes les conditions prévues à l'art. 6, al. 2, ou si :
a. lors de la survenance de l'invalidité, leur père ou mère compte, s'il s'agit d'une personne étrangère, au moins une année entière de cotisations ou dix ans de résidence ininterrompue en Suisse et si
b. eux-mêmes sont nés invalides en Suisse ou, lors de la survenance de l'invalidité, résidaient en Suisse sans interruption depuis une année au moins ou depuis leur naissance. Sont assimilés aux enfants nés invalides en Suisse les enfants qui ont leur domicile et leur résidence habituelle en Suisse, mais qui sont nés invalides à l'étranger, si leur mère a résidé à l'étranger deux mois au plus immédiatement avant leur naissance (...).
1.2 En procédure fédérale, le litige porte uniquement sur la question de savoir si la condition de la durée minimale de cotisations (<ref-law>) est ou non réalisée.
Ainsi que l'office recourant l'avait déjà indiqué dans sa réponse au recours cantonal, la résolution de cette question requiert, au préalable, de déterminer si K._, qui compte plus d'une année de cotisations, est bien la mère de M._. Dans l'affirmative, selon l'office AI, le droit à la prestation litigieuse serait à l'évidence ouvert; à défaut, il ne le serait pas.
2. En tant que le dispositif renvoie la cause au recourant pour instruction complémentaire et nouvelle décision au sens des considérants, le jugement entrepris doit être qualifié de décision incidente qui ne peut être attaqué qu'aux conditions de l'<ref-law> (<ref-ruling> consid. 4.2 p. 482). En tant qu'il constate un lien de filiation maternelle entre K._ et M._ et reconnaît expressément que la condition de la durée minimale d'une année de cotisations prévue à l'<ref-law> est remplie, le jugement attaqué contient une constatation de fait impérative destinée à l'autorité inférieure et se prononce sur une des conditions du droit à la prestation, si bien que cette dernière n'a plus aucune latitude de jugement pour la suite de la procédure. En cela le recourant subit un préjudice irréparable au sens de l'<ref-law> et il y a lieu d'entrer en matière sur le recours (cf. <ref-ruling> consid. 5.2 p. 483).
3. 3.1 Les premiers juges ont constaté que l'office AI n'avait pas respecté la procédure de préavis (cf. <ref-law>) avant de statuer. Ils n'ont toutefois pas annulé la décision administrative pour ce motif, mais en raison du fait que le lien de filiation contesté devait être tenu pour acquis dès lors que l'authenticité des documents officiels congolais versés au dossier (un jugement du 12 janvier 2002 ainsi qu'un acte de naissance établi le 2 avril 2002) n'était pas remise en cause et que rien ne permettait de renverser la présomption d'exactitude des faits retenus dans ces actes.
3.2 A cet égard, l'office recourant fait grief au Tribunal administratif d'avoir appliqué faussement l'<ref-law> (recte : <ref-law>); à son avis, cette disposition légale ne concerne que les titres publics (registres et actes authentiques) prévus par le CC, le CO et la législation civile (de droit fédéral) accessoire. D'autres documents, allègue-t-il, ne bénéficient pas de cette force probante.
Le recourant rappelle ensuite qu'il avait requis l'audition de K._ par le Tribunal administratif, en qualité de témoin. Comme le Tribunal n'a pas donné suite à sa requête, il estime que son droit d'être entendu a été violé, car il a ainsi été empêché de faire administrer la preuve de la réalité du lien de filiation. En s'appuyant sur une jurisprudence abondante, le recourant observe qu'il avait d'autant plus de raisons de vouloir s'assurer de la réalité de la filiation maternelle (qui avait été constatée par le jugement supplétif du 12 janvier 2002), que la République démocratique du Congo est en proie à une telle corruption qu'elle figure sur les circulaires fédérales des Etats dont les documents sont les plus sujets à caution. Le recourant en déduit que le jugement attaqué retient à tort que la filiation est établie sur des « documents officiels dont l'authenticité n'est pas remise en cause ».
3.3 Quant à M._, elle se rallie au jugement attaqué. A son avis, la réalité du lien de filiation ne fait aucun doute, celui-ci ayant d'ailleurs été dûment établi par le jugement congolais du 12 janvier 2002. Elle se réfère en outre à un jugement du Tribunal administratif du canton de Neuchâtel du 13 mai 2005, dans une affaire qui l'opposait au Service des étrangers et Département de l'économie publique, où l'autorité judiciaire aurait admis qu'une analyse ADN ne serait pas suffisamment fiable pour établir la filiation maternelle. Elle allègue enfin que les mises en demeure des 7 et 26 juillet 2006 étaient inopérantes, notamment en raison du fait que les consentements requis n'avait pas été sollicités comme l'art. 33 al. 2 de la loi fédérale sur l'analyse génétique humaine du 8 octobre 2004 (LAGH, RS 810.12) le prévoit, que sa mère et elle-même ne possédaient pas les profils d'ADN demandés et qu'il n'avait pas été fait mention du fait que l'AI supporterait le coût des expertises.
4. 4.1 En reconnaissant l'existence d'un lien de filiation maternelle entre K._ et M._, le Tribunal administratif a procédé à une constatation de fait qui, en principe, lie le Tribunal fédéral (<ref-law>).
Dès lors que l'office recourant s'en prend à la manière dont ce fait déterminant a été constaté, en alléguant qu'il résulte de l'application erronée d'une règle de preuve ainsi que de la violation de son droit d'être entendu, il convient d'examiner la pertinence de ce grief. On rappellera à cet égard que le recours ne peut critiquer les constatations de fait que si les faits ont été établis de façon manifestement inexacte ou en violation du droit au sens de l'art. 95, et si la correction du vice est susceptible d'influer sur le sort de la cause (cf. <ref-law>).
4.2 A propos du profil d'ADN qu'il avait demandé, l'office AI avait précisé, dans sa réponse au recours cantonal, que les enjeux d'un tel examen pour le Service des migrations n'étaient de loin pas identiques aux siens, car le litige porte sur la prise en charge par l'AI d'une formation professionnelle initiale dont le coût global pourrait excéder la somme de 120'000 fr. Confronté au refus de K._ de se soumettre à un tel examen, l'office AI avait requis l'édition des dossiers du Service des migrations ainsi que l'audition de la prénommée par le Tribunal administratif. L'examen de ces dossiers avait amené l'office AI à conclure que le lien de filiation en cause faisait à l'évidence défaut. En particulier, il avait fait observer que dans deux procès-verbaux des 31 mai et 30 juin 1995, K._ - qui était à cette époque entendue en qualité de requérante d'asile - avait déclaré aux autorités suisses qu'elle n'avait pas de descendance.
Le Tribunal administratif ne s'est pourtant pas exprimé sur la contradiction patente existant entre les déclarations de K._ (en 1995) et le jugement congolais (rendu en 2002), que l'office AI avait mise en exergue. En jugeant que les documents congolais officiels établissaient de toute manière l'existence du lien de filiation, sans discuter les objections du recourant, la juridiction cantonale a renoncé arbitrairement à administrer tout autre moyen de preuve pertinent, violant ainsi non seulement le droit de l'une des parties au procès d'être entendue (art. 29 al. 2 Cst.), mais contrevenant également à l'obligation du juge des assurances sociales d'établir d'office les faits déterminants (art. 61 let. c LPGA) et de motiver sa décision. Ainsi que le recourant l'observe à juste titre, il est erroné de conclure en l'état que la filiation est constatée sur la base de « documents officiels dont l'authenticité n'est pas remise en cause », car les incertitudes liées à la force probante des documents congolais étaient renforcées aussi bien par le défaut de collaboration de K._ que par le dossier du Service des migrations (voir les procès-verbaux des 31 mai et 30 juin 1995, précités, ainsi qu'un procès-verbal de saisie par les douanes suisses d'un passeport angolais falsifié établi au nom de S._, qui lui avait été adressé par voie postale en avril 2000).
5. La requête de l'office AI tendant à obtenir les profils d'ADN entrait dans le cadre de ses prérogatives légales (cf. <ref-law>) et constituait assurément, en pareilles circonstances, un moyen approprié pour statuer sur le droit aux prestations. L'<ref-law>, en vigueur depuis le 1er avril 2007, règle expressément les modalités de tels examens.
La décision de refus des prestations d'assurance, que l'office AI a signifiée dans sa décision du 16 octobre 2006, est motivée par le défaut de collaboration de K._ à l'instruction de la cause. L'administration n'a toutefois pas respecté la procédure d'audition préalable prévue à l'<ref-law>, car K._ n'a pas été invitée à se déterminer. Quant au curateur de M._, l'office AI lui a bien adressé un projet de décision (du 13 octobre 2006), mais il a statué trois jours plus tard sans attendre l'échéance du délai de 30 jours qu'il lui avait accordé pour se déterminer, violant aussi le droit de M._ d'être entendue (voir l'arrêt B. du 27 janvier 2006, I 658/04, connu de l'office recourant).
Il s'ensuit que la cause sera renvoyée à l'office AI afin qu'il en reprenne l'instruction, en veillant au respect des règles instaurées par l'<ref-law> (s'il entend poursuivre dans cette voie) et les art. 73bis et 73ter RAI, puis statue à nouveau sur la demande de prestations.
6. Les frais judiciaires seront mis à la charge de l'intimée qui succombe (<ref-law>).
7. L'intimée ne dispose pas des moyens financiers pour s'acquitter des frais judiciaires et des honoraires de Me Oesch.
Elle remplit ainsi les conditions du droit à l'assistance judiciaire pour la procédure fédérale (<ref-law>). L'attention de l'intimée est attirée sur le fait qu'elle devra rembourser la caisse du Tribunal fédéral si elle devient en mesure de le faire ultérieurement (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est admis en ce sens que le jugement du Tribunal administratif du canton de Neuchâtel du 18 juillet 2007 et la décision de l'Office de l'assurance-invalidité du canton de Neuchâtel du 16 octobre 2006 sont annulés, la cause étant renvoyée audit office pour qu'il procède conformément aux considérants.
2. L'assistance judiciaire est accordée à l'intimée et Me Jean Oesch est désigné comme avocat d'office.
3. Les frais judiciaires, arrêtés à 500 fr., sont mis à la charge de l'intimée. Ils sont toutefois supportés provisoirement par la caisse du Tribunal.
4. Les honoraires de Me Oesch sont fixés à 1'500 fr. (y compris la taxe sur la valeur ajoutée) pour la procédure fédérale et seront supportés provisoirement par la caisse du Tribunal.
5. Le présent arrêt est communiqué aux parties, à Me Oesch, au Tribunal administratif du canton de Neuchâtel, à l'Office fédéral des assurances sociales, ainsi qu'à K._.
Lucerne, le 8 octobre 2008
Au nom de la IIe Cour de droit social
du Tribunal fédéral suisse
p. le Président: Le Greffier:
Borella Berthoud