In Brazil:
To be head of state of Australia you cannot be Australian, as that post is currently reserved for the English Monarch.
Well, strictly speaking I suppose it is remotely possible for an Australian to become English Monarch due to a rather long bad luck streak in the line of inheritance for the throne, but in practical terms they will always be English.
Mexico has a similar set of limited offices as Brazil, and used to be even stricter: until 1993 the Presidency and those in the immediate line of succession had to have both parents be also born citizens.
Haiti had a requirement that not only you were a citizen, but that you never held another citizenship.
In the case of a lot of the Central American countries there is the fact of a real history of attempts to “plant” outsiders as rulers (e.g. Maximillian) and of filibusteers and carpetbaggers attempting takeovers (e.g. Walker), informing their framers’ intentions.
The Dutch legal situation is complicated. I’ll try to summarize:
Citizens are allowed to vote at the age of 18 for the house of commons. This includes inhabitants of Bonaire, St Eustatius and Saba. Also, citizens of Curaçao, Aruba and St Maarten who have the Dutch nationality and have lived for 10+ years in the Netherlands.
For provincial elections, any “Netherlander” of 18 years or older living in the province is allowed the vote. [What “Netherlander” means is obscure to me, but I assume naturalization is good enough].
Municipal elections: “Netherlanders” [again] over the age of 18, living in the municipality + EU citizens living there + anyone over 18 who’s been living there for 5+ years.
Water boards (one of the first real democratic systems in western Europe): anyone over 18 living in the area.
As for passive rights [that is, being electable]:
Both houses of parliament and provincial states: “Netherlanders” over 18.
Municipalities: “Netherlanders” + EU citizens + anyone living in the country for 5+ years, who’s over 18 living in the area.
Since you’re being technical, there’s a few points to consider about your assertion. One, there is no English Monarch any more. Elizabeth II’s current British title is “Her Majesty Elizabeth the Second, by the Grace of God, of the United Kingdom of Great Britain and Northern Ireland, and of Her other Realms and Territories, Queen, Head of the Commonwealth, Defender of the Faith.”
Secondly, there are plenty of non-UK citizens in line for the Throne. The Norwegian Royal Family, for instance, are in the line of succession. So, if something untimely should happen to the first 60-odd people on the list, Harald V can finally reunite the Danelaw with Norway…
In Japan you cannot hold a position of power in the public service over Japanese citizens unless you yourself are a Japanese citizen. This means, for example, that you can’t be chief janitor in a public hospital unless you are a Japanese citizen.
Well I did mean that the Monarch is going to be English, rather that the Monarch of England. I don’t expect an heir is much more likely to be allowed to be born in Northern Ireland than in Norway or Australia.
And as for Norway, well, yes, but the OP was about whether the head of state needed to be born in the country in question, which in my case was Australia. That ours could be born in Norway is just as bad as in England.
Thailand does. The current prime minister, although Thai from a fairly high-powered family, was born in Newcastle, England, and the opposition is now trying to make a big deal out of that. (He was also educated at Eton and Oxford.) It’s a bit convoluted, but I think they’re trying to claim he’s British because he never formally renounced British citizenship – which neither he nor anyone else in his family ever claimed – upon becoming an adult. You also can’t be a member of parliament without at least a bachelor’s degree.
Used to be that new Thai citizens were not allowed to vote. I believe they can now after five years.
I actually did mean (but stupidly forgot to explain) “native-born”, but feel free to keep discussing. 
De Valera was born to an Irish mother and was living in Ireland at the time of independence. Under the Constitution proclaimed on Irish independence, that was enough to make him an Irish citizen on the same terms as someone born on Irish soil.
BTW, the US constitutional term is “natural born”, not “native born”.
Or even a volunteer fireman. There is at least one naturalized Japanese citizen who is a politician.
Well seeing as we are being technical, the nationality “English” doesn’t exist in any meaningful way, so no requirement/expectation of the Monarch being English exists in any meaningful way either.
Now if you were talking about the Monarch being British …
Someone born in England is no longer English?
I wasn’t saying there’s a (formal) requirement that the Monarch be English, but that nevertheless things will be arranged so that they will be, if at all possible.
“English” is a matter of identity and not nationality. It hasn’t existed as a nationality for a long time. We’re all Brits, no matter how much certain Welsh and Scots want to complain. Northern Ireland is a bit more complex, they can be Irish if they want to be.
To put it in a simple fashion, good luck finding a passport that says “Nationality: English” in it.
However, there is no legal requirement that the PM be an MP. Nor do they have to be a member of the House of Lords. (Sir Alec Douglas-Home holds the double distinction of being the last PM to be a member of the House of Lords, and the last PM to not be a member of either house of Parliament.)
Wikipedia asserts that “It is a constitutional convention that only a Privy Counsellor can be appointed Prime Minister.” I think this is overstating the case somewhat, since the fact that someone wasn’t a PC wouldn’t operate to prevent them being offered the office of PM; they’d just be appointed to both.
Membership of the Privy Council has an indirect relevancy to the legal qualifications to become Prime Minister, though; the Act of Settlement 1700 restricts membership to Commonwealth citizens, and citizens of the Republic of Ireland. Although there’s no formal requirement for a Prime Minister to be a member of the Privy Council, it’s very hard to see how the job could be done without being one.
The same restriction in the Act of Settlement also applies to someone enjoying "any Office or Place of Trust either Civill or Military. I have no idea whether this would apply to a Minister of the Crown; if it does, then that’s the closest thing to a legal qualification for the office of PM that we currently have. Still, it’s a pretty wide restriction!
Unfortunately the language of the Act of Settlement is very confusing, because of the way it was “repealed” by the British Nationality Act 1948; so the former Act still has on the face of it a restriction against those who are not natural-born British subjects, even though this restriction cannot possibly apply to anyone.
There’s a possible additional restriction. Section 18 of the Roman Catholic Relief Act 1829 (commonly known as the Catholic Emancipation Act) is still in force:
This is relevant because the prime minister is involved in the appointment of the Church of England’s bishops and archbishops. Should the situation arise, though, it would presumably be no great difficulty to have (say) the Home Secretary take over the role, as I don’t think the prime minister’s involvement in these appointments has any statutory basis.
I think most of us understood it. As ruadh pointed out, the US says “natural-born”. Other nations make it clearer by using the term such as, for example, “Mexican by birth”, to make clear the meaning is you were born with the citizenship/nationality.
I just came across an obituary of the president of Fiji, which had this relevant info:
But Indo-Fijians are native-born citizens of Fiji. What they are is an ethnic minority in the country.
As far as I know Michaëlle Jean had French citizenship, obtained through her husband. I don’t remember if she actually had Haitian citizenship as well. And it should be mentioned that both her and Dion didn’t need to renounce their other citizenships to hold their positions. They just did because some people made an issue of it.
Indeed. But the text of the OP was:
So it’s relevant to note that in some countries they wouldn’t even be thrilled about your children or grandchildren becoming a leader, let alone you.
Historically the Indian population of South Africa encountered similar problems.
I think this might apply regarding ethnic Russians in one or more of the three Baltic republics, as well.