Faits : A. X._ et Y._, tous deux de nationalité brésilienne, se sont mariés en 2001 au Brésil. De leur union est issue A._, née en 2002. A.a. Les parties ont divorcé au Brésil en 2006 et la garde sur l'enfant a été confiée à la mère, avec un droit de visite en faveur du père. Alors que la mère était titulaire de la garde de la fille, elles ont résidé en Suisse en 2007 et sont rentrées au Brésil en mars 2008. Au cours de la période passée en Suisse, la mère a eu une deuxième fille, issue d'un nouveau mariage. Par la suite, la mère et l'enfant ont fait plusieurs séjours en Suisse, autorisés par le père, mais celui-ci s'est opposé à un nouveau départ en février 2011, estimant que ces allers-retours n'étaient pas dans l'intérêt de leur fille. A.b. Par " décision judiciaire brésilienne portugaise " du 3 juillet 2012, la garde de l'enfant a été transférée au père, au motif que le bien de l'enfant le nécessitait. B. Alors que l'enfant vivait avec son père et sa belle-mère au Brésil, à la demande de celle-ci qui souhaitait vivre en Suisse avec sa mère, le père a autorisé l'enfant à séjourner en Suisse avec sa mère pour une période de huit mois, du 31 octobre 2014 au 1 er juillet 2015. La mère et l'enfant ne sont pas retournées au Brésil depuis lors. B.a. Par requête reçue au greffe de la Cour de justice de la République et canton de Genève le 28 avril 2016, X._ a requis le retour immédiat de sa fille. Par déterminations du 10 juin 2016, l'enfant représentée par sa curatrice, de même que la mère, ont toutes deux conclu au rejet de la requête en retour et au déboutement du requérant de toutes ses conclusions. La Chambre civile de la Cour de justice a tenu audience le 24 août 2016 et a procédé à l'audition des parties. Lors de cette audience, le père a contesté avoir fait subir à sa fille de mauvais traitements et a exposé que des négociations avaient eu lieu entre les parents préalablement au dépôt de la requête en retour, ce qui expliquait le délai entre la date de retour fixée et le dépôt de la requête. La mère a soutenu que la période de huit mois prévue dans l'autorisation devait permettre de voir si leur fille s'intégrait bien dans son nouvel environnement, ce qui était le cas, mais le père est revenu sur sa promesse que l'enfant puisse rester en Suisse. Elle a affirmé qu'une plainte avait été déposée au Brésil à la suite des blessures infligées à leur enfant et que le père et la belle-mère avaient admis avoir frappé celle-ci. Enfin, l'enfant, entendue seule par la Chambre civile de la Cour de justice, s'est exprimée en français et a déclaré s'être bien intégrée à Genève, avoir beaucoup travaillé pour obtenir un bulletin scolaire excellent et souhaiter rester auprès de sa mère avec laquelle elle a d'excellentes relations. Lors de cette audience, le conseil du requérant a remis à la cour cantonale l'autorisation requise, dont il ressort que les deux parents ont en commun la " responsabilité parentale " selon le droit brésilien, même si la garde a été accordée exclusivement à l'un d'eux, et que les parents doivent consentir à tout déplacement du lieu de résidence habituelle de l'enfant. B.b. Statuant par arrêt du 9 septembre 2016, communiqué aux parties par plis recommandés le 14 septembre 2016, la Chambre civile de la Cour de justice de la République et canton de Genève a rejeté la demande de retour de l'enfant A._, formée le 26 avril 2016 par le père. C. Par acte du 26 septembre 2016, X._ exerce un recours en matière civile au Tribunal fédéral. Il conclut principalement à l'annulation de l'arrêt entrepris et à sa réforme en ce sens que le retour immédiat de sa fille A._ auprès de lui au Brésil est ordonné, et que la violation de l'art. 11 de la Convention de La Haye par l'autorité précédente est constatée. A titre subsidiaire, le père conclut à l'annulation de l'arrêt attaqué et au renvoi de la cause à l'autorité précédente. Au préalable, le recourant requiert le bénéfice de l'assistance judiciaire pour la procédure fédérale, comprenant la désignation de son avocate en qualité de conseil d'office. Le lendemain, le 27 septembre 2016, le recourant a transmis quatre attestations de la Cour de justice de S ão Paulo, datées du 22 septembre 2016. Invitées à déposer des observations sur le recours, la mineure - représentée par sa curatrice - a conclu au rejet du recours et requis le bénéfice de l'assistance judiciaire pour la procédure fédérale; la mère a conclu à l'irrecevabilité des pièces produites par le recourant et au rejet du recours; l'autorité précédente s'est référée aux considérants de son arrêt. Par écritures du 28 novembre 2016, le recourant a déposé une réplique, modifiant ses conclusions subsidiaires, en ce sens qu'il conclut dorénavant à l'annulation de l'arrêt attaqué et au renvoi de la cause à l'autorité précédente " pour nouvelle instruction en sollicitant la mise en oeuvre d'un rapport d'évaluation sociale auprès du Service de la protection des mineurs de la République et canton de Genève "; puis, à titre plus subsidiaire, à l'annulation de l'arrêt attaqué et au renvoi de la cause à l'autorité précédente. Le recourant joint à sa réplique deux courriers du Service de la protection des mineurs des 7 et 17 novembre 2016 concernant l'autre fille de l'intimée, ainsi qu'une copie du bordereau de pièces que l'intimée a produit le 21 novembre 2016 dans le cadre d'une procédure pendante devant la Chambre civile de la Cour de justice concernant sa deuxième fille.