Faits:
A. X._ et dame Y._ se sont mariés le 24 mars 1995. De leur union sont issus trois enfants, nés respectivement le 19 mai 1995, le 5 septembre 1997 et le 18 avril 2002.
Par jugement du 7 août 2006, le Président du Tribunal d'arrondissement de Lausanne a prononcé le divorce des époux, ratifiant pour le surplus la convention des parties sur les effets accessoires, dont le chiffre IV prévoyait notamment que le père contribuerait à l'entretien de chacun de ses enfants à raison de 1'500 fr. par mois jusqu'à l'âge de 15 ans révolus et de 1'600 fr. par la suite et jusqu'à la majorité de l'enfant, son indépendance financière ou l'achèvement d'une formation professionnelle, pour autant que celle-ci entre dans les conditions de l'<ref-law>.
B. Le 27 juin 2007, X._ a saisi le Tribunal civil de l'arrondissement de l'Est vaudois d'une requête de mesures préprovisionnelles d'extrême urgence ainsi que de mesures provisionnelles tendant à la réduction à 400 fr. par mois au maximum des aliments en faveur de chaque enfant. Cette requête a été rejetée en raison de l'absence de saisine du juge du fond, décision confirmée par l'arrêt du Tribunal cantonal du 8 février 2008, contre lequel aucun recours n'a été formé.
C. Le 12 octobre 2007, X._ a ouvert une action en modification du jugement de divorce, concluant à ce que la contribution en faveur de chacun de ses enfants soit réduite à dire de justice, mais au maximum à 400 fr. par mois, avec effet rétroactif au 1er mai 2007. Son ex-épouse s'y est opposée.
Par jugement du 8 août 2008, la Présidente du Tribunal civil de l'arrondissement de l'Est vaudois a rejeté la demande, sous suite de frais et dépens.
Statuant le 25 février 2009, la Chambre des recours du Tribunal cantonal du canton de Vaud a partiellement admis le recours interjeté par X._. Elle a réformé le jugement entrepris notamment en ce sens qu'elle a partiellement admis la demande en modification du jugement de divorce et fixé à 1'260 fr., allocations familiales en sus, dès le 1er août 2008, les aliments dus mensuellement pour chaque enfant jusqu'à l'âge de 15 ans et à 1'360 fr. jusqu'à la majorité ou l'indépendance financière ou encore jusqu'à l'achèvement d'une formation professionnelle entrant dans les prévisions de l'<ref-law>; elle l'a confirmé pour le surplus.
D. X._ exerce un recours en matière civile et un recours constitutionnel subsidiaire au Tribunal fédéral. Dans ses deux écritures, il conclut à ce que la contribution à l'entretien de chaque enfant soit arrêtée à 800 fr. du 1er juin 2007 au 1er mai 2008 inclusivement, à 1'260 fr. du 1er mai 2008 jusqu'à l'âge de quinze ans révolus et à 1'360 fr. jusqu'à la majorité, voire au-delà. Il demande aussi la révision, en sa faveur, des frais et dépens cantonaux.
Dame Y._ propose le rejet du recours. L'autorité cantonale se réfère à ses considérants.

Considérant en droit:
1. Le Tribunal fédéral examine d'office et librement la recevabilité des recours qui lui sont soumis (<ref-ruling> consid. 1.1 p. 3).
1.1 Le recours a été déposé en temps utile (<ref-law>) contre une décision finale (<ref-law>) prise en dernière instance cantonale et sur recours par le tribunal supérieur du canton de Vaud (<ref-law>) dans une affaire civile (<ref-law>) de nature pécuniaire (cf. <ref-ruling> consid. 2; également: <ref-ruling> consid. 2 p. 395) dont la valeur litigieuse atteint 30'000 fr. (art. 51 al. 4 et 74 al. 1 let. b LTF). Le recourant a pris part à la procédure devant l'autorité précédente et a un intérêt juridique à la modification de la décision attaquée (<ref-law>). Le recours en matière civile est donc en principe recevable, de telle sorte que le recours constitutionnel ne l'est pas (<ref-law>).
1.2 Devant le Tribunal fédéral, le recourant limite son recours à la période courant du 1er juin 2007 au 31 juillet 2008 (14 mois). Selon ses conclusions, la contribution à l'entretien de chacun de ses enfants devrait être réduite - rétroactivement - à 800 fr. par mois du 1er juin 2007 au 30 avril 2008 (11 mois), puis à 1'260 fr. entre le 1er mai et le 31 juillet 2008 (3 mois). A ce stade de la procédure, la réduction de la contribution à 1'260 fr. dès le 1er août 2008 jusqu'à l'âge de 15 ans et à 1'360 fr. au-delà - ce qui correspond à ce qui a été alloué par le Tribunal cantonal - n'est plus litigieuse.
2. L'autorité cantonale a constaté que le recourant réalisait, au moment du prononcé du divorce, un revenu moyen mensuel net de 12'500 fr. en qualité d'agent d'assurance indépendant. Entre le 7 mars 2007 et le 29 février 2008, il s'était trouvé sans emploi et avait perçu des indemnités de chômage. Celles-ci s'étaient élevées à 7'119 fr. 75 de mars à décembre 2007 et à 8'400 fr. 05 de janvier à février 2008. Dès le 1er mars 2008, le recourant avait été engagé comme agent d'assurance pour le compte d'une compagnie. Pour les neuf premiers mois d'activité, il avait touché en moyenne 9'799 fr. 75 auxquels s'étaient ajoutées - à l'exception des deux premiers mois d'activités (mars et avril 2008) - des commissions. Il avait ainsi réalisé en définitive un revenu mensuel moyen de 10'500 fr.
Sur la base de ces faits, la Chambre des recours a retenu qu'une diminution durable de revenu de 12'500 fr. à 10'500 fr., soit une réduction de 16 %, était intervenue à partir du 1er mai 2008; elle a jugé qu'une telle modification était notable au sens de la jurisprudence et justifiait une réduction à 1'260 fr. de la contribution en faveur de chaque enfant. Pour arriver à ce chiffre, elle a appliqué la proportion entre les pensions et les revenus du débirentier arrêtée dans le jugement de divorce (36 % de 10'500 fr. : 3 enfants).
Elle a ensuite considéré que la modification du jugement de divorce pouvait intervenir au plus tôt à la date d'ouverture de l'action en modification, soit le 12 octobre 2007; se référant à son arrêt du 8 février 2008, elle a rappelé que le dépôt de la requête de mesures provisionnelles le 27 juillet 2007 n'y changeait rien. Elle a cependant retenu, en définitive, la date du prononcé du jugement de première instance, soit le 1er août 2008. Elle a jugé que, lors de l'ouverture d'action, la situation de chômage du demandeur n'était pas encore durable et que, par ailleurs, la situation de la défenderesse, qui percevait un revenu de 4'300 fr. par mois, était nettement moins favorable que celle de son ex-mari, même au chômage, de telle sorte que la restitution des contributions utilisées pendant la durée du procès ne pouvait être équitablement exigée d'elle.
3. Le recourant reproche à la Chambre des recours de ne pas avoir fixé au 1er juin 2007 la date de modification du jugement de divorce. Il soutient qu'elle a violé le droit fédéral (art. 129 al. 1, 134 al. 4, 137 et 286 al. 1 CC) en écartant toute réduction de la contribution d'entretien avant le dépôt de l'action au fond, le 12 octobre 2007, ainsi qu'en fixant le point de départ de la modification au jour du jugement de première instance, à savoir le 1er août 2008.
3.1 Sous le couvert de la violation de l'<ref-law>, le recourant critique en réalité - de façon irrecevable - l'arrêt du Tribunal cantonal vaudois du 8 février 2008, devenu définitif faute de recours au Tribunal fédéral, auquel s'est référée la Chambre des recours pour refuser tout effet rétroactif antérieurement au 12 octobre 2007. Celui-là avait jugé que les mesures provisionnelles tendant à modifier un jugement de divorce étaient exclusivement régies par le droit fédéral, qu'elles s'inscrivaient nécessairement dans le cadre d'une action pendante et que, dans le cas particulier, en l'absence du dépôt par l'ex-mari d'une action en modification de son jugement de divorce, la requête de mesures provisionnelles déposée devait être rejetée.
Quoi qu'il en soit, il résulte de ce qui précède qu'aucune procédure tendant à une modification du jugement de divorce n'était pendante entre les parties avant le 12 octobre 2007, date du dépôt d'une telle demande par le recourant. Toute l'argumentation juridique de ce dernier se fondant précisément sur l'existence d'une telle litispendance, elle est dénuée de tout fondement.
3.2 L'<ref-law>, applicable par renvoi de l'<ref-law>, permet au père, à la mère ou à l'enfant de saisir le juge afin d'obtenir la modification ou la suppression de la contribution à l'entretien de l'enfant fixée par le juge du divorce. Cette modification ou suppression suppose que des faits nouveaux importants et durables surviennent, qui commandent une réglementation différente. La procédure de modification n'a en effet pas pour but de corriger le premier jugement, mais de l'adapter aux circonstances nouvelles (cf. <ref-ruling> consid. 2.7.4 p. 199/200; <ref-ruling> consid. 3a p. 178; <ref-ruling> consid. 4b p. 292). Parmi les changements qui peuvent être pris en considération figurent notamment l'invalidité, la maladie de longue durée, la retraite et la perte d'un emploi (PETER BREITSCHMID, Commentaire bâlois, 3ème éd., no 13 ad <ref-law>; PHILIPPE MEIER/MARTIN STETTLER, Droit de la filiation, 4ème éd., nos 583 s.; STEPHAN WULLSCHLEGER, FamKommentar Scheidung, 2005, no 7 ad <ref-law>; CYRIL HEGNAUER, Commentaire bernois, no 81 ad <ref-law>). S'agissant plus précisément de ce dernier point, la jurisprudence estime qu'une période de chômage supérieure à quatre mois ne peut plus être considérée comme étant de courte durée; dans une telle situation, il convient en principe de tenir compte des indemnités de chômage effectivement perçues (arrêt 5P. 445/2004 du 9 mars 2005 consid. 2.3 concernant la modification de mesures protectrices de l'union conjugale). Dans tous les cas, la question de savoir si la période de chômage est durable dépend des circonstances concrètes de chaque cas d'espèce, en particulier de la situation économique (arrêt précité, consid. 2.2).
3.2.1 Il ressort de l'arrêt entrepris que, dès mars 2007, le recourant s'est trouvé sans emploi pendant douze mois. Lorsque, en octobre 2007, il a saisi le juge de la présente demande en modification du jugement de divorce, il avait déjà subi une période d'inoccupation de plus de sept mois. Il est certes exact que, dans de nombreuses situations, le chômage constitue un état passager qui ne justifie en principe pas une modification du jugement de divorce (cf. arrêt du Tribunal cantonal du canton de Bâle-Campagne du 10 décembre 2002 consid. 2b publié in FamPra 2003 p. 732). Tel n'était cependant pas le cas en l'espèce. La période de chômage s'est étendue sur une année - durée qu'il convient de prendre entièrement en considération, indépendamment de la date de saisine du juge de la modification - et a finalement induit une réduction de 16 % des revenus du recourant par rapport à ce qu'il percevait au moment du divorce. Dans de telles conditions, l'autorité cantonale ne pouvait, sans violer le droit fédéral, juger que le chômage du recourant ne constituait pas un changement durable de circonstances. De même, elle ne pouvait exclure une modification du jugement de divorce, motif pris que le recourant avait surmonté ces difficultés en retrouvant un travail. En effet, si la période de chômage a pris fin le 29 février 2008, elle a néanmoins eu pour conséquence une réduction notable des revenus de l'intéressé.
Cela étant, les juges cantonaux auraient dû tenir compte de la période prolongée de chômage du recourant pour envisager, en raison de ce motif-là, une modification du jugement de divorce. Il convient toutefois d'examiner encore si cette violation du droit fédéral a une influence sur l'issue du recours, dans la mesure où l'autorité cantonale a refusé de faire remonter l'effet rétroactif à l'ouverture de l'action non seulement en raison de ce motif mais aussi parce qu'une restitution des contributions utilisées pendant la durée du procès ne pouvait pas être équitablement exigée de l'épouse.
3.3 Le juge de l'action en modification d'un jugement de divorce peut fixer le moment à partir duquel son jugement prend effet selon son appréciation et en tenant compte des circonstances du cas concret (<ref-ruling> consid. 4c p. 369 et les références). En principe, la jurisprudence retient, au plus tôt, la date du dépôt de la demande. Lorsque le motif pour lequel la modification est demandée se trouve déjà réalisé à ce moment, il ne se justifie normalement pas, du point de vue de l'équité, de faire remonter l'effet de la modification à une date ultérieure. Le créancier de la contribution doit en effet tenir compte d'un risque de réduction ou de suppression de la rente dès l'ouverture d'action (arrêt précité, consid. 4c/aa p. 370 et la jurisprudence citée). Selon les circonstances, il est toutefois possible de retenir une date postérieure, par exemple le jour du jugement, notamment lorsque la restitution des contributions accordées et utilisées pendant la durée du procès ne peut équitablement être exigée (arrêt précité, consid. 4c/bb p. 371 et les références). Cette dernière situation suppose que le crédirentier, sur la base d'indices objectivement sérieux, ait pu compter pendant la durée de la procédure avec le maintien du jugement d'origine; il s'agit ainsi d'un régime d'exception (WALTER BÜHLER/KARL SPÜHLER, Commentaire bernois, no 189 in fine ad <ref-law>).
3.3.1 La cour cantonale a fixé l'entrée en vigueur de la modification du jugement de divorce au 1er août 2008, date du jugement de première instance. Retenant que la situation de l'intimée était nettement moins favorable que celle du recourant, elle a considéré que la restitution des contributions utilisées pendant la durée du procès ne pouvait être équitablement exigée.
3.3.2 Le recourant soutient qu'aucune circonstance exceptionnelle ne permettait à la cour cantonale de s'écarter du principe selon lequel la modification du jugement de divorce intervient à l'ouverture de l'action. Il taxe de manifestement inexact la constatation selon laquelle les contributions d'entretien destinées aux enfants auraient été « utilisées pendant la durée du procès ». Sur ce point, il résulte de l'arrêt attaqué que le recourant, sous réserve de paiements irréguliers à concurrence de 7'187 fr. 70, ne s'est pas acquitté de la contribution globale de 4'500 fr. par mois en faveur des enfants entre mai 2007 et mai 2008. Il est en outre établi que, dans un premier temps, il s'est vu refuser le versement des indemnités de chômage, avant d'obtenir gain de cause auprès du Tribunal cantonal. Il les a ainsi perçues, rétroactivement, le 9 juillet 2008, date que la cour de céans est en mesure de retenir en application de l'<ref-law> (sur la question du complètement des constatations par le Tribunal fédéral: arrêt 4A_290/2007 du 10 décembre 2007 consid. 5.1 publié in SJ 2008 I p. 346).
En d'autres termes, sous réserve de quelques montants, le recourant n'a pas versé les contributions d'entretien en faveur des enfants de mai 2007 à mai 2008, situation compatible avec l'absence de versement, durant cette période, de toute indemnité de chômage. Plus particulièrement, pendant la période de chômage déterminante en l'espèce, soit du 1er juin 2007 au 29 février 2008, l'intimée n'a reçu du recourant que quelques versements pour une somme totale de l'ordre de 2'300 fr. Dans ces circonstances, il ne pouvait être fait référence à une restitution des contributions déjà utilisées par l'intimée, puisque les montants effectivement perçus (2'300 fr.) étaient largement inférieurs à ceux qui avaient été alloués en procédure. L'autorité cantonale ne pouvait dès lors fonder sa décision sur le caractère inéquitable d'une telle restitution.
Les juges cantonaux ont certes encore mentionné la différence de situation économique des parties, soulignant que celle de l'intimée était nettement moins favorable que celle du recourant. Cette seule référence ne suffisait toutefois pas pour écarter la règle selon laquelle la modification du jugement de divorce remonte en principe à la date d'ouverture de l'action lorsque le motif de la modification est, comme en l'espèce, déjà réalisé à ce moment. En tant qu'il s'agissait d'apprécier un régime d'exception, l'autorité cantonale devait se montrer exigeante quant à la réalisation de ces conditions. Pour ne pas l'avoir fait, elle a aussi violé le droit fédéral.
3.3.3 Cela étant, il faut considérer comme déterminante la date du dépôt de la demande de modification du jugement de divorce, soit le 12 octobre 2007 (cf. supra, consid. 3.1), époque à laquelle le motif de réduction des contributions était déjà réalisé (cf. supra, consid. 3.2). S'agissant de la quotité de la réduction, il faut tenir compte du fait que, entre cette date et le 1er août 2008, les revenus du recourant ont fluctué. En prenant les montants - non contestés - retenus par la cour cantonale et en appliquant la proportion des revenus pour les trois enfants (36%) - telle que arrêtée et non critiquée devant la cour de céans -, la contribution mensuelle à l'entretien de chacun d'eux doit être fixée de la manière suivante: 850 fr. du 12 octobre 2007 au 31 décembre 2007 (12 % de 7'119 fr. 75), 1'000 fr. du 1er janvier au 29 février 2008 (12 % de 8'400 fr. 05), 1'175 fr. du 1er mars au 30 avril 2008 (12 % de 9'799 fr. 75) et 1'260 fr. du 1er mai au 31 juillet 2008 (12 % de 10'500 fr.).
4. Vu l'issue de la procédure, l'intimée, qui succombe, supportera les frais judiciaires et versera des dépens au recourant (art. 66 al. 1 et 68 al. 1 et 2 LTF). Il y a lieu de renvoyer la cause à l'autorité cantonale pour nouvelle décision sur les frais et dépens de la procédure cantonale (art. 67 et 68 al. 5 LTF).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours constitutionnel subsidiaire est irrecevable.
2. Le recours en matière civile est partiellement admis dans la mesure où il est recevable et l'arrêt attaqué est réformé en son chiffre II comme suit:
«X._ contribuera à l'entretien de chacun de ses trois enfants par le paiement, dès le 12 octobre 2007, en mains de dame Y._ le premier de chaque mois, allocations familiales en sus, de:
- 850 fr. par mois du 12 octobre 2007 au 31 décembre 2007;
- 1'000 fr. par mois du 1er janvier au 29 février 2008;
- 1'175 fr. par mois du 1er mars au 30 avril 2008;
- 1'260 fr. par mois dès le 1er mai 2008 et jusqu'à l'âge de 15 ans révolus; - 1'360 fr. par mois dès lors et jusqu'à la majorité ou l'indépendance financière ou encore jusqu'à l'achèvement de la formation professionnelle pour autant que celle-ci entre dans les prévisions de l'<ref-law>».
3. Le chiffre III du dispositif de l'arrêt attaqué est annulé et la cause est renvoyée à l'autorité précédente pour nouvelle décision sur les frais et dépens des instances cantonales.
4. L'arrêt attaqué est confirmé pour le surplus.
5. Les frais judiciaires, arrêtés à 2'500 fr., sont mis à la charge de l'intimée.
6. Une indemnité de 3'000 fr. à payer au recourant à titre de dépens, est mise à la charge de l'intimée.
7. Le présent arrêt est communiqué aux parties et à la Chambre des recours du Tribunal cantonal du canton de Vaud.
Lausanne, le 30 octobre 2009
Au nom de la IIe Cour de droit civil
du Tribunal fédéral suisse
La Présidente: La Greffière:
Hohl Jordan