Faits : A. C._, née en 2008 à Distrito Central, département Francisco Morazan (Honduras) est issue de la relation hors mariage qu'ont entretenue A._ (1983) et B._ (1990), tous deux de nationalité hondurienne, entre août 2006 et mars 2008. Les parties s'opposent sur les circonstances de leur séparation. A.a. Par décision intitulée "acte de remise" du 26 mars 2008, le Tribunal des mineurs de Tegucigalpa (Honduras) a remis l'enfant C._ à sa mère et a fait interdiction au père de s'approcher de sa fille. Par jugement du 11 juin 2008, le Tribunal des mineurs du département de Francisco Morazan (Honduras) a déclaré l'enfant C._ dans une situation de risque social et a ordonné le retour de l'enfant au foyer de sa mère, afin qu'elle lui apporte les soins et l'attention nécessaires. A.b. En septembre 2010, la mère a quitté le Honduras pour venir travailler et gagner de l'argent en Suisse. Elle a confié sa fille C._ à la grand-mère paternelle de l'enfant et transférait de l'argent à celle-ci pour l'entretien de sa fille et à titre de rémunération pour les soins voués à sa fille. Au Honduras, l'enfant C._ vivait auprès de sa grand-mère, avec son père, sa tante, son oncle et ses cousins. Elle dormait dans le lit de sa grand-mère, vu le manque de place. Scolarisée, elle se rendait à l'école le matin et restait à la maison l'après-midi pour y faire ses devoirs avec sa famille, mais ne pouvait pas sortir en raison des dangers encourus. Son père se trouvait à la maison ou allait travailler. La mineure C._ avait des contacts avec sa mère par téléphone et internet. B. La mère est retournée au Honduras en été 2015. Elle a emmené la mineure C._ à Genève le 24 juillet 2015. L'enfant a quitté le Honduras au moyen d'une autorisation de sortir du pays datée du 21 juillet 2015, portant une signature libellée au nom du père et munie d'un certificat d'authenticité de la signature établi par le barreau des avocats du Honduras. L'enfant C._ vit depuis lors à Genève avec sa mère, sa tante, son oncle et son cousin, et elle y est scolarisée. Elle a des contacts téléphoniques avec son père et sa grand-mère au Honduras. B.a. Le 12 février 2016, A._, domicilié au Honduras, a saisi la Cour de justice d'une requête en vue du retour immédiat de sa fille C._ auprès de lui au Honduras. Il a également requis des mesures provisionnelles tendant au dépôt des documents d'identité de l'enfant et l'interdiction à la mère de quitter le territoire suisse avec l'enfant. Ces mesures provisionnelles ont été ordonnées d'accord entre les parties le 23 mai 2016. Le 25 février 2016, l'Autorité centrale du Honduras a émis une attestation constatant l'illicéité du départ de l'enfant C._ en date du 24 juillet 2015, au motif que la mineure aurait quitté le pays au moyen de faux documents et sans autorisation du père. Par réponse du 21 mars 2016, la mère s'est opposée à la requête en retour de l'enfant. Le 30 mars 2016, elle a sollicité que l'attestation émise le 25 février 2016 par l'Autorité centrale du Honduras soit déclarée nulle et le 6 mai 2016, elle a demandé à la Cour de justice de surseoir à statuer sur le retour de l'enfant dans l'attente de la procédure en nullité de ladite attestation du 25 février 2016, engagée devant les autorités administratives du Honduras. La mère a exposé que le père n'était pas titulaire du droit de garde sur sa fille et a soutenu que les démarches du père avaient pour seul objectif de pouvoir à nouveau bénéficier de l'argent qu'elle versait à la grand- mère paternelle de l'enfant pour l'entretien de cette dernière. Le 25 avril 2016, le curateur désigné à la mineure a demandé à la Cour de justice de surseoir au renvoi de l'enfant, sollicitant au préalable divers documents des autorités honduriennes. Lors d'une audience le 9 mai 2016, les parties et la curatrice ont été entendues et ont persisté dans leurs conclusions respectives. La mère a indiqué à cette occasion que la dernière décision rendue par les autorités judiciaires du Honduras au sujet de l'enfant était celle du 11 juin 2008. Les 13 et 17 juin 2016, le SPMin a procédé à l'audition de la mineure C._, ainsi que la mère et les enseignantes de l'enfant. Dans son rapport du 27 juin 2016, le SPMin a exposé que la mineure avait fait preuve d'une grande capacité d'adaptation à son nouvelenvironnement et qu'elle souhaitait rester à Genève. L'enfant a également expliqué qu'au Honduras, son père était parfois "un peu méchant" et allait s'alcooliser lorsqu'il recevait son salaire et, dans ces circonstances, il l'avait tapée une fois sur la jambe. Dans une écriture du 21 juillet 2016, le père a persisté dans sa requête. La curatrice de l'enfant a conclu, à titre principal, à ce que la Cour de justice renonce à ordonner le retour de la mineure au Honduras, par conséquent à ce qu'elle rejette la requête du père en retour de l'enfant. A titre subsidiaire, elle a conclu à ce que la Cour de justice sollicite divers documents concernant la portée des décisions honduriennes, ainsi qu'un rapport social sur les conditions de vie de la mineure au Honduras. B.b. Par arrêt du 14 septembre 2016, communiqué aux parties le 15 septembre 2016 par pli recommandé, 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 C._, formée le 12 février 2016 par le père et débouté les parties de toutes autres conclusions. C. Par acte du 29 septembre 2016, A._ interjette un recours en matière civile au Tribunal fédéral. Il conclut à l'annulation de l'arrêt entrepris et, principalement, à sa réforme en ce sens que le retour immédiat de l'enfant C._ auprès de son père au Honduras est ordonné, subsidiairement, au renvoi de la cause à l'autorité précédente. Au préalable, le recourant sollicite d'être mis au bénéfice de l'assistance judiciaire pour la procédure fédérale, comprenant la désignation de son conseil en qualité d'avocate d'office. Invitées à déposer des observations sur le recours, l'enfant, représentée par son curateur, et la mère ont toutes deux conclu au rejet du recours et sollicité d'être mise au bénéfice de l'assistance judiciaire pour la procédure fédérale. Pour sa part, l'autorité précédente s'est référée aux considérants de son arrêt.