How about scripting, say, 10 settler spawns for the AI. They would be separated into 3-4 groups (each group triggering at a different year, separated by periods of a hundred years). Then, one of the spawns in the group would be chosen at random.
Example:
It is year 1600. Three spawns are scripted: a settler on Samoa, Vanuatu or the Salomon Isles. One of them is chosen at random, say, Samoa. AI Polynesia gets a settler on that tile.
This is all, obviously, to enable variance in settling patterns from game to game. Additionally, conditions could be added to make sure the AI isn't getting a settler while unstable etc. As for the groups, another way to do it would be to have only once group, from which a spawn is removed upon happening.