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 (art. 9 al. 3 let. a LAI) 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. 