In my attempts, I have rarely suffered from stability problems. I think at one point, my stability was +13; +3 was domestic and +10 economy.
Although it's an interesting way of playing, it sometimes tends to get boring, because essentially the build order is pagan temple first and then wait for your borders to pop.
I think this would serve as an example. Here, I played on 600 AD map, spawned Phoenicia on Easter Island and began the game with only knowledge of polytheism, fishing and sailing:
As you can see, it is probably 1600 AD now, and it took that whole time to get four cities in. The main problem is the production; There simply isn't enough to quickly get up those Pagan temples. At the same time, it's hard to use slavery since there isn't enough happiness resources in the region to deal with the unhappiness.
One of my most productive cities was my capital. there was a fish resource and a harbour, so I was able to get it to a population of 7 before the plague, and have 4-5 citizen specialists. A random event gave me whales in that area, so that was a fortunate addition, if only I had optics.
I'd say it provided an interesting challenge. Protestantism spread to one of my cities which caused it to be unhappy for a while. I then had to trade a stone (Which I made at Easter Island) for gems, which turned out quite nicely.
I think if I start at 3000 B.C, I would have more time to progress.
I've also been thinking;
What map changes do we need to have as a result of adding the Polynesian civ?