Not seeing any great data source out there I already, I reviewed the constitutions of 48 countries. I looked for the requirements to hold their chief executive position. These countries were selected in a non-random and non-projectible way.
I will update this answer as I review more constitutions.
Below is a map summarizing my findings, as well as showing the countries that I have reviewed to date:
40 of 48 countries require citizenship
For 40 of the 48 countries I reviewed, I could see a constitutional requirement that included citizenship. 22 of these 48 required natural-born citizenship, although the exact formulation of "natural-born" varied.
Countries which require citizenship to become the chief executive are colored red on the map; dark red countries require natural-born citizenship.
3 countries do not appear to require citizenship
For 4 of the 48 countries, their constitution makes it possible to have a non-citizen be the chief executive. These are discussed below.
Article 44 of the Australian Constitution outlines the reasons a person may be disqualified from running for a federal legislative seat. The Prime Minister is selected from among elected legislators, so they are required to be meet those same conditions.
In particular, someone becomes disqualified if they are:
a subject or a citizen ... of a foreign power
Notably, this doesn't mean they would have to be a citizen of Australia, they just can't be a citizen of anywhere else. This opens the door to a stateless Prime Minister of Australia, or perhaps someone who has renounced their citizenship in another country.
Bosnia and Herzegovina
Bosnia/Herzegovina has a kind of triumvirate: three Presidents each elected from a different territory and of a different ethnicity (see Article 5). The three Presidents are:
- A Croat elected from B&H
- A Bosniac elected from B&H
- A Serb elected from the Serbian Republic
The Constitution is silent on what it means to be "elected from" one of these territories. It does not lay down a citizenship requirement, opening the door to the possibility of a non-citizen of the correct ethnicity being elected to the Presidency.
Note: The Constitution mentions an elections law that will define more of the election system. It was available online, but offered no more clarification on this issue.
Croatia's constitution does not have any formal requirements for their chief executive, except being elected.
5 countries: Other
Five countries were coded as "other". In two cases I couldn't tell, because I couldn't find an English copy of the current constitution (Benin and the Ivory Coast). Two was excluded for not having an elected federal executive (Brunei and Comoros). One was excluded for not being a sovereign nation (Aruba).