Hm, beats my idea. I was thinking of a series of missionaries, with each successful adventure winning over one of the barbarian tribes. My model has the disadvantage of 'power spiral', where there have to be tougher enemies in the later modules just to pose a challenge to the formerly successful players.
Adventure seeds you may wish to consider:
1) The migrating tribes have to cross through Salamander controlled territory/waters. To make things worse, the salamanders in question have recently put down a slave revolt, and are looking for replacements.
2) While sailing near the Teeth of Pthunlos, the tribe is approached by [octopi-demons] who wish to migrate with them. Is it a trick? Will they offer to convert to get a deity on their side? Are they agents of Zhamaz? How do PCs who accept the offer deal with the undines, or worse, Fate? It might even be cool if the mundanes have already accepted the offer in the name of the PC, thus miring them in trouble.
3) Members of an Elder Race try to join the PCs religion. Which is less of a hassle, turning away worshippers who may become hostile over their rejection, or dealing with the negotiating tactics of the racial gods of that species?