After conquering and nuking way too many civs, I finally won a domination victory with Polynesia. (Regent/Marathon, no way I could've done this on any higher difficulty)
This time I made quite a few screenshots so this will be a relatively long post.
After playing (and losing) many games by settling New Zealand and then going to Australia (this strategy was based on a Polynesian science victory for an older (maybe 1.12?) version of DoC, which I found on some Chinese forum), I finally found out that the trick was settling the only spot in the southern part of New Guinea that you can reach with a settler as your second city.
This allowed me to reach other civs much faster than using the New Zealand approach, which did wonders to my technological situation; I even managed to trade seafaring to India! Also, since I could get OB with them so early on, Hinduism spread to one of my cities by turn 369. This boosted our relations a lot, and I think I ended up getting 2-3 free techs from them. Sadly the Tamils did exceptionally great in this game, and they managed to collapse India at some point in the 13th century.
I beelined Cartography after getting Feudalism (=Tributaries=free commerce and stability), and even though the Scandinavians got it like a century before I did, they didn't go for the conqueror events. So I sent out a caravel as soon as I could, then razed the Inca capital and took all their cities and capitulated the Aztecs who would've respawned as Mexico anyways. Later I had to realize that the Inca will respawn without any core city as well, but at that point I could kill them again in about 3 turns.
I also switched to slavery for the slave trading money. It was pretty hard to sell all my slaves in this game for some reason, but I still managed to do it and got quite a bit of money out of it.
On turn 887, Japan and Indonesia declared war on me. They didn't bring any troops except some ships which I sunk fairly quickly, so I made peace with Japan and capitulated Indonesia. Also, the Dutch settled a pretty useless city in New Zealand, which was conveniently next to my city on the island. So I ended up stealing pretty much all their gold and some of their techs.
Then I declared war on them due to a random wedding event. I mainly did this so that I could make peace with them when they got the Indonesian conqueror event. This resulted in their troops being pushed into Australia, and their stack proceeded to stay on my continent until I finally eradicated them.
I got quite a few great people, but I saved most of them for the Industrial era, where I had a hard time staying stable, and having a somewhat acceptable economy. This was one exception though, as I really wanted that tech trading bonus (Polynesian tech modifiers are horrible).
Also, I finally capitulated Japan on turn 1089. They are pretty much the only strong AI in East-Asia that usually manages to stay alive, so I took the opportunity while they were still pretty weak.
At this point I probably should've gone for America, but I didn't. This turned out to be a big mistake when half of the world declared war on me after a congress. America took about two Aztec cities, which I reconquered after taking all Portugese colonies in China. My army then started marching towards San Francisco, but more than half of it was annihilated by an unexpected American SoD so I finally made peace.
At this point the game kept CtDing on wine, but luckily I have a copy of Win10 on my computer so I was able to keep playing.
About 100 turns later I refused a congress decision which wanted me to give Cantao back to Portugal. This was actually a nice opportunity to "decolonize" some cities in my area without ruining my relations.
Montezuma couldn't really do anything on the American front, and being the total failure he is, he kept using the mercenary archers he recruited against me hundreds of years ago (even though I gave him iron). He ended up collapsing to core, but as a nice side effect, America collapsed from overexpansion as well.
I reconquered their territory later. Meanwhile, Italy declared war on me and destroyed my Austrian peace vassals, thus lowering my stability (I was still in tributaries. Actually, I stayed in tributaries in the entire game). They even took Berlin...
Killing Italy was harder than I expected: I forgot to train any air units, and Italian fighters kept shooting at my stack. Additionally, my only source of oil was what I demanded from Austria, so I couldn't train any, either. I did manage to get them eventually in a rather brutal fashion.
They weren't willing to capitulate. At least I got their vassals in the end. Spain as well, for despite the impressive size of their Empire, they were technologically way behind me.
Then China declared war on me for some reason. At this point I had so many planes that I could kill all their garrisons without a single land unit. They didn't have a stack either so taking them out was trivial. After that, I capitulated Thailand.
Also, Indonesia collapsed and then respawned, taking Havaiki (the city I mentioned on the first picture) But my navy was completely destroyed in the war against Italy, so they got away with it.
Then I noticed that Canada took the lead on the scoreboard. Since I was originally going for a time victory, this was a bit scary. I evaluated my options, and decided that starting a nuclear war against them would probably not work out very well. However, as I was already in state party, I could practically take any city I wanted. So I started doing that.
First, I capitulated Iran.
Then Arabia. Then Egypt, but Egypt collapsed so I took all of their cities. I was planning to collapse Morocco as well, but they were going strong even after I took most of their cities in the Maghreb so I accepted their capitulation.
(also, I had to set the graphics to low after a MAF. sorry for the exceptionally bad quality of the following screenshots)
This wasn't quite enough for a domination victory, so I proceeded to take most Turkish cities and subsequently all of Russia. Meanwhile in Asia I was working on destroying Korea, which I did just after dropping a nuke on them. Also, even though I let them have one of my cities, the Indonesians still declared war on me. After I nuked their capital, they realized that peace is a better option.
Sweden declared war on me because of a defensive pact with Russia so I nuked them as well.
Finally, I got my population percentage past the domination limit (my territory was past it for 20 turns at that point, mostly because of my vassals). But just to be sure...
PS:
I forgot to mention this but late game tech speed was horrendously slow. Even Super-Canada wasn't close to getting to the Mars, and the only competent AI in regards to teching was England (and the Vikings, but they collapsed in the 16th century I think), which was in the Global era in the 19th century, but then collapsed. Even Japan didn't really have techs I could've stolen in the end, despite the fact that I gave them pretty much all techs I researched for free. I guess one has to play on higher levels for an actually efficient espionage economy.
And tributaries is a must for Domination. I had a +20 foreign stability bonus from it in the end, which was enough for not having to care about stability.