What are the prerequisites for changing government in Europa Universalis IV?

Solution 1:

Ack, finally found it by thrashing. Maybe some of you guys already knew this, but I did not... As it turns out, EU IV provides a different, entirely separate way of changing your government type to Western for the first time. It's on the new Native Ideas page all the way at the bottom after completing all of the native ideas, a new button stating, "Reform Government" - Once you press that your government reforms.

It also looks like @Nix was correct both in noting that the nation to the North was actually French-Canada, a colonial nation, and that this fact did not matter. Once I finally found the correct button I went back and replayed the game from an earlier point where I was only connected to French Canada, and not the Netherlands, and I was still given the option to Reform Government.

^{Click image for larger version.}

Solution 2:

This is a restriction on the tribal nations. If you have the DLC, you will eventually be able to reform your government – but not untill you are exposed to western countries. From what I can understand from your question, you already fulfill all requirements (point 1-3).

Your tech level shouldn't matter untill you decide to westernize – but in order to that, you must have reformed your government. Ergo is your point 4 irrelevant, as fas as I can tell.

Requirements
- All native ideas filled.
- A core province next to a Western nation's core province.

Effects
- All native ideas lost.
- All native buildings are lost (also the already built ones are lost), the standard building interface replaces it.
- Tech level advances to 90% of the Western nation's, rounded down.(?)
- Government changes to the form of government that borders the nation, if you border a kingdom then you will reform into a kingdom, same for republics and theocracies.
- Allows westernizing the country, if the regular conditions are met (at least 8 technologies behind the western neighbour)

See more on the EU4 Wiki.