Faits: A. Par jugement du 29 avril 2010 du Tribunal de première instance de Genève, le divorce des époux X._ (1964) et Y._ (1969) a été prononcé. Le Tribunal a notamment attribué à la mère l'autorité parentale et la garde sur les enfants du couple, A._, née en 1998, et B._, né en 2002, réservé un large droit de visite du père et condamné celui-ci à contribuer à l'entretien de chacun des enfants par le versement, allocations familiales non comprises, de la somme indexée de 800 fr. jusqu'à ce que l'enfant ait atteint l'âge de 10 ans et de 1'000 fr. ensuite et jusqu'à la majorité, voire au-delà, mais au plus tard jusqu'à l'âge de 25 ans, en cas d'études sérieuses et régulières. B. Le 17 novembre 2011, le père a déposé une demande en modification du jugement de divorce, complétée le 28 juin 2012, tendant à ce que son obligation d'entretien en faveur de ses enfants soit supprimée avec effet au 1 er novembre 2011. Il a allégué, à l'appui de sa demande, que sa situation financière s'était sensiblement péjorée depuis cette date, alors que celle de la mère s'était " probablement considérablement améliorée ". Sur mesures provisionnelles, le père a conclu à la suspension des contributions d'entretien dès le 22 juin 2012 et jusqu'à l'entrée en vigueur du jugement au fond. La mère a conclu au rejet des mesures provisionnelles et, par réponse du 12 octobre 2012, a également conclu au déboutement du père sur le fond. B.a. Par ordonnance de mesures provisionnelles du 18 octobre 2012, le Tribunal de première instance a astreint le père à contribuer à l'entretien de ses enfants par le versement, allocations familiales non comprises, de la somme de 100 fr. par enfant, à compter du 1 er juillet 2012. B.b. Statuant par jugement du 30 janvier 2013, le Tribunal de première instance a modifié le jugement de divorce en ce sens que le père a été condamné à contribuer à l'entretien de ses enfants par le versement, allocations familiales non comprises, de la somme de 100 fr. par enfant, dès le 1 er juillet 2012, jusqu'à la majorité voire au-delà, mais au plus tard jusqu'à l'âge de 25 ans, en cas d'études sérieuses et régulières. Le 5 mai 2013, la mère a formé appel, concluant à l'annulation du jugement de première instance, partant, implicitement à ce que le père verse une contribution de 1'000 fr. par mois et par enfant, dès le 1 er juillet 2012. Le père a conclu au rejet de l'appel de la mère et formé un appel joint tendant principalement à la suppression totale de son obligation d'entretien de ses enfants, avec effet au 1 er novembre 2011, ainsi qu'au remboursement par la mère des paiements effectués en trop à partir de cette date, subsidiairement à ce que la contribution d'entretien de 100 fr. par mois et par enfant soit confirmée, mais avec effet au 1 er novembre 2011, avec remboursement par la mère du trop perçu. La mère a conclu au rejet de l'appel joint. B.c. Par arrêt du 18 octobre 2013, communiqué aux parties le 24 octobre 2013, la Chambre civile de la Cour de justice du canton de Genève a admis l'appel et l'appel joint, modifié le jugement de divorce du 29 avril 2010 en ce sens qu'à partir du 1 er juillet 2012, le père est astreint à contribuer à l'entretien de ses enfants par le versement, allocations familiales non comprises, de la somme de 800 fr. par enfant, dès l'âge de 10 ans et jusqu'à la majorité, voire au-delà en cas d'études sérieuses et régulières, et a enfin débouté les parties de toutes autres conclusions. C. Par acte du 25 novembre 2013, 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 l'obligation d'entretien des enfants est supprimée, avec effet au 1 er novembre 2011, et qu'il soit ordonné à la mère de restituer les montants versés en trop depuis le 1 er novembre 2011, subsidiairement au renvoi de la cause à l'autorité précédente. Le père sollicite au préalable l'octroi de l'effet suspensif à son recours et requiert d'être mis au bénéfice de l'assistance judiciaire pour la procédure fédérale. Invitées à se déterminer sur la requête d'effet suspensif, la mère a conclu à son rejet et l'autorité précédente s'en est rapportée à justice. D. Par ordonnance du 11 décembre 2013, le Président de la IIe Cour de droit civil du Tribunal fédéral a partiellement admis la requête du père en ce sens que l'effet suspensif a été octroyé pour les contributions dues jusqu'à la fin octobre 2013, mais non pour les montants dus à partir du 1 er novembre 2013. La mère, invitée à déposer des observations sur le fond, a conclu au rejet du recours. L'autorité cantonale a déclaré se référer aux considérants de son arrêt. 