I'm not even attempting to answer the whole question, just want to give example of a country which managed to avoid the bloody religious wars of Germany or France ( other answer implies that it was the only way to reach religious tolerance ). That country was Polish - Lithuanian Commonwealth, which spanned a large chunk of Europe, and was mostly Catholic, with its kings being exclusively Catholic.
The first codified example of tolerance in the kingdom of Poland was the Statue of Kalisz, announced in 1264. It not only guaranteed Jews the freedom to practice their religion, it actually went much further – one sample paragraph:
Should a Jew be taken to court, not only a Christian must testify
against him, but also a Jew, in order for the case to be considered
valid.
The statue was later confirmed by kings of Polish – Lithuanian Commonwealth.
In the next century, tolerance guarantees were given to Orthodox Christians, Armenians, and Muslim Tatars.
In 1525 Polish king agreed to a plan of establishing formerly Catholic Duchy of Prussia as his Lutheran fief.
In the XVI century protestant ideas gained supporters in Polish-Lithuanian Commonwealth proper. As a result in 1573 Polish parliament passed Warsaw Confederation act, which gave the protestant denominations the same rights as Catholics. From now on, every newly elected Polish king had to accept those provisions.
So, Poland avoided religious wars of Germany. Another result was that Polish – Lithuanian Commonwealth became attractive destination for “heretics” from other countries, primarily from Germany. It also harbored the biggest Jewish population in the world, and the most orthodox versions of Judaism developed there.
I don't find any particular reason for the direction that Poland (it's kings, gentry and clergy) went regarding religious tolerance, except from pure pragmatism.
But it's just an example country, perhaps someone with more knowledge will comment on the situation in Ottoman Empire and other European states.