In Germany, any citizen over 40 is eligible to be elected president. France's constitution doesn't specify that the president be born in the country. "Any citizen over 50 years" can be president of Italy.
Many Latin American countries -- like their neighbor to the north -- do specify that the president be native-born. Mexico's president, for instance, has to be a citizen by birth with at least one Mexican parent and 12 years' residency. Brazil's president must also be born in the country.
Peru has even had its own birther controversy, thanks to media reports that former president Alberto Fujimori was born in Japan. The president produced his Peruvian birth certificate for analysis in 1997, but some doubts persist.
Iran's president not only has to be of "Iranian origin," he must exhibit "trustworthiness and piety." Presumably, being a secret Christian would be a disqualification from that office.
It's theoretically possible for someone who wasn't born in Britain, or even a citizen, to be elected prime minister. The prime minister is a member of a parliament who is chosen by members of his or her party. According to British law, an MP must be "18 years of age, and a British citizen, or citizen of a Commonwealth country or the Republic of Ireland." It would probably be pretty tough for someone from Ireland or the Bahamas to get the job, but there's nothing legally stopping them. To date, only one British prime minister -- Bonar Law, originally of New Brunswick -- has been born outside the British Isles.
In any event, if Obama decides he's sick of being president of a country where 20 percent of the people don't believe he's a citizen, and he's willing to go through the trouble of becoming a citizen and resident somewhere else, he does have a few options.