Faits: A. Le 22 juin 2006, le Service du Tuteur général de Genève a adressé au Procureur général une dénonciation. Il y expliquait que l'enfant B.X._, née le 21 novembre 1997, avait confié à la mère de sa famille d'accueil, A._, que A.X._, "sa vraie maman, lui avait mis le doigt dans la fente" lorsqu'elle l'avait rencontrée au Point de Rencontre le 7 juin 2006. Dans une attestation médicale, datée du 16 juin 2006, la Dresse B._, pédiatre de l'enfant, constatait ce qui suit: "J'ai vu B.X._ (née le 21.11.1997) le 13.6.06 pour des démangeaisons et douleurs vulvaires. A l'examen (facile) : érosion (env. 1 cm) au niveau de la vulve du côté droit, vulve plutôt enflammée, hymen intact. J'ai proposé plusieurs explications refusées par B.X._ qui m'a dit: "c'est maman qui m'a fait ça". En date du 10 juillet 2006, une audition de B.X._ a été effectuée en présence d'une psychologue. Elle a révélé, en substance, que sa mère "lui faisait des trucs dans les parties interdites" lorsqu'elles se rencontraient au Point de Rencontre et qu'elle l'accompagnait aux toilettes, qu'elle la regardait et la touchait, et même lui avait "touché le sexe, à l'intérieur", qu'"elle avait les ongles des mains longs et sales et que suite à cela, son sexe était tout rouge et la démangeait". Cette audition a fait l'objet d'un enregistrement DVD ainsi que d'une retranscription écrite. B. Le 9 février 2007, A.X._ a été inculpée d'actes d'ordre sexuel avec des enfants (art. 187 CP) et de contrainte sexuelle (art. 189 CP). Une expertise de crédibilité a été confiée au Dr C._, de l'Institut universitaire de médecine légale. L'expert a conclu que les allégations de la fillette - telles que relevées dans le document vidéo - n'étaient pas crédibles. Il soulignait que les dires de l'enfant s'inscrivaient dans un conflit entre ses "mères", dans lequel l'enfant se sentait obligée de prendre parti. Elle éprouvait un soulagement à ne plus rencontrer sa mère biologique - qu'elle appréciait peu -, du fait de ses déclarations, et échappait ainsi au conflit de loyauté. Les visites au Point de Rencontre semblaient en effet problématiques pour la mère de sa famille d'accueil, qui lui avait reproché la tenue (ventre à l'air), le maquillage ou ses ongles peints qu'elle arborait lors desdites visites. Le 29 juin 2007, le Juge d'instruction a entendu la pédiatre qui avait examiné l'enfant B.X._ le 13 juin 2006. Selon ce médecin, la lésion vulvaire était "fraîche", c'est-à-dire qu'elle datait d'un à trois jours avant son examen. Il s'agissait d'une griffure superficielle, qui impliquait un grattage avec des ongles, même courts. La pédiatre ne pouvait pas déterminer la cause de la lésion. Par la suite, le Juge d'instruction a interrogé différentes personnes vivant dans l'entourage de B.X._ (éducatrices, assistants sociaux, psychothérapeute, institutrice, marraine "de coeur"). Aucune d'entre elles n'a constaté directement de geste étrange ou déplacé émanant de A.X._. En particulier, aucune des deux éducatrices présentes au Point de Rencontre n'a remarqué quoi que ce soit de particulier au cours de la visite du 7 juin 2006. Toutefois, aux dires des témoins D._ (assistant social responsable du dossier de B.X._ au Service de protection des mineurs), E._ (soeur de la mère de la famille d'accueil) et F._ (marraine "de coeur"), l'enfant a relaté, à plusieurs reprises, spontanément et de manière constante, que, lorsqu'elle était aux toilettes, "sa maman lui avait mis le doigt dans la fente", ce qui lui avait fait mal et lui avait occasionné des démangeaisons. C. Le 15 septembre 2008, le Procureur général genevois a ordonné le classement de la procédure faute de prévention suffisante. Dans une lettre adressée au mandataire de l'enfant B.X._, il expliquait que la pédiatre qui avait examiné B.X._ avait constaté une érosion vulvaire sans pouvoir en déterminer l'origine. En outre, les éducatrices au Point de Rencontre n'avaient rien observé d'anormal dans le comportement de la mère biologique. Enfin, l'expertise de crédibilité concluait que les allégations d'abus proférées par la fillette n'étaient pas crédibles. Dans ces conditions, il convenait donc de renoncer à toute poursuite. A.X._ a recouru contre l'ordonnance de classement auprès de la Chambre d'accusation du canton de Genève et conclu au prononcé d'un non-lieu. Le 25 février 2009, la Chambre d'accusation a rejeté le recours. D. Contre cette dernière ordonnance, A.X._ dépose un recours en matière pénale devant le Tribunal fédéral. Se plaignant d'arbitraire dans l'établissement des faits et dans l'application des art. 198 et 204 CPP/GE, ainsi que de la violation de la présomption d'innocence, elle conclut au prononcé d'un non-lieu, sous suite de frais et dépens. En outre, elle sollicite l'assistance judiciaire. Appelée à se déterminer, l'intimée B.X._ a conclu au rejet du recours. Le Procureur général du canton de Genève et le Tuteur général s'en sont remis à l'appréciation du Tribunal fédéral, et la cour cantonale s'est référée aux considérants de son ordonnance.