Faits: A. A.a X._, né le 26 octobre 1957, de nationalités togolaise et française, et Y._, née le 16 juillet 1961, de nationalité française, se sont mariés à St-Prex (VD) le 5 novembre 1994. Trois enfants sont issus de cette union: A._, née le 14 février 1995, B._, né le 24 janvier 1997, et C._, née le 21 janvier 1999. X._ est aussi le père d'un quatrième enfant, D._, née en République togolaise le 26 août 2006. Statuant le 11 août 2000 sur requête commune des époux, le Tribunal du district de Morges a prononcé le divorce des parties, ratifié leur convention sur les effets accessoires de celui-ci et donné acte au mari de son engagement de verser mensuellement à l'épouse, détentrice de l'autorité parentale et du droit de garde sur les enfants, des contributions à l'entretien de chacun d'eux d'un montant de 300 fr. jusqu'à l'âge de 5 ans, 350 fr. de 5 à 13 ans et 400 fr. de 13 ans à la majorité, allocations familiales non comprises. A.b Le 4 octobre 2007, le père a formé une action en modification du jugement de divorce, concluant à la diminution de la contribution d'entretien en faveur de chaque enfant à 100 fr. par mois jusqu'à l'âge de 14 ans, puis à 150 fr. par mois jusqu'à la majorité. Il s'est d'abord limité à invoquer la péjoration de sa situation financière à la suite de la naissance de son quatrième enfant et l'amélioration de celle de son ex-épouse, puis s'est en outre prévalu de la perte de son emploi. Y._ s'est opposée à la demande, arguant que la situation de son ex-mari, hormis la naissance d'un quatrième enfant auquel il n'établissait pas envoyer régulièrement de l'argent, n'avait pas considérablement changé depuis le jugement de divorce et que la perte de son emploi, intervenue après le dépôt de la requête, n'était que passagère, s'agissant d'une résiliation pour justes motifs. A.c Par ordonnance de mesures provisoires du 24 juillet 2008, le juge de paix du district de Morges a ratifié l'accord des parties selon lequel la mère renonçait à son droit de garde sur son fils B._, ce droit étant confié au Service de protection de la jeunesse de l'Est vaudois avec pour mission de placer l'enfant chez son père pour une durée de trois mois; il n'est pas contesté que la mesure a été reconduite pour une nouvelle période de trois mois par ordonnance de mesures provisoires du 15 octobre 2008, dans l'attente d'une décision définitive. A.d Statuant le 21 mai 2008 sur demande de la mère, le Tribunal d'arrondissement de La Côte a ordonné à tout débiteur du père de prélever directement la somme de 1'100 fr. sur ses indemnités, rentes, salaires ou allocations, et de la verser à la mère. Le montant précité a toutefois été réduit à 500 fr. par arrêt de la Chambre des recours du Tribunal cantonal du canton de Vaud du 6 octobre 2008. B. Par jugement du 10 septembre 2008, le Tribunal de première instance du canton de Genève a débouté le père de toutes ses conclusions tendant à la modification des contributions prévues par le jugement de divorce en tant qu'elles concernaient la période antérieure au 3 août 2008, et a suspendu l'instruction de la cause pour la période postérieure au 3 août 2008 jusqu'à droit jugé par le tribunal compétent du district de Morges quant à l'attribution de la garde du mineur B._. Le père a appelé de ce jugement, concluant à ce qu'il soit uniquement astreint à verser des contributions mensuelles à l'entretien de chacune de ses filles aînées, d'un montant de 100 fr. jusqu'à l'âge de 14 ans et de 150 fr. de 14 ans à la majorité, allocations familiales non comprises, dès le 1er septembre 2007. Il demandait en outre que lui soit réservé son droit de réclamer une contribution pour l'entretien de son fils. Une audience de plaidoiries a été appointée au 27 janvier 2009. Par courrier du 21 janvier 2009, dans lequel elle demandait que son absence soit excusée, la mère, qui s'était préalablement opposée à l'appel, a fait part de sa décision de retourner s'installer dans la région parisienne, dont elle est originaire, à partir de septembre 2009, et de demander que la garde de son fils lui soit à nouveau attribuée dès juillet 2009. Par arrêt du 20 mars 2009, la Chambre civile de la Cour de justice du canton de Genève a modifié le jugement du 10 septembre 2008 en ce sens que le père a été débouté de toutes ses conclusions en modification des contributions d'entretien fixées par le jugement de divorce. C. Par acte du 11 mai 2009 X._ exerce un recours en matière civile au Tribunal fédéral contre l'arrêt du 20 mars 2009, en reprenant principalement ses conclusions formulées en appel. Subsidiairement, il conclut au renvoi du dossier à la Cour de justice pour nouvelle décision au sens des considérants. L'intimée propose le rejet du recours. L'autorité cantonale s'est référée aux considérants de son arrêt. Les deux parties sollicitent par ailleurs le bénéfice de l'assistance judiciaire. 