Ted Cruz hopes to join the list.
To those five you can add two more recent PMs.
Julia Gillard was born in Wales and Tony Abbott was born in England
There’s the joke that Austria’s greatest triumph was convincing the world that Beethoven was Austrian and Hitler wasn’t.
AFAIK, every single one of the co-princes of Andorra were born outside of the country. Haakon VII of Norway was a rare (outside of the Vatican) elected monarch and was Danish, the son of the Danish King and the next king’s younger brother.
Toomas Hendrik Ilves, President of Estonia, born in Sweden, raised in New Jersey. I suppose you could count everyone in the Baltic states, most of the -stans, etc. because it was technically USSR, but I don’t think that’s what you want. Stalin was born in what is now Georgia though.
Since this thread was started, Australia has had two prime ministers born in Britain (although I think a child born today in the same circumstances as Tony Abbott would be an Australian citizen at birth).
The earliest Prime Ministers of Israel, including the first of them, David Ben-Gurion, were born before Israel even existed. The same could be said for the first several American presidents (although, of course, they were born in the colonies that became the United States).
Any time a new country is created, its first top-dog leader, and probably the first several, will necessarily be born before that county existed.
Jomo Kenyatta, Idi Amin (both born in British East Africa, led Kenya and Uganda respectively) and Robert Mugabe (born in Rhodesia, leads Zimbabwe) all meet the letter of this.
Emperor Baldwin of Constantinople was, IIRC, born in Flanders. Emperor Baldwin of Jerusalem was born in Lorraine.
Simon Bolivar, born in Caracas Venezuela, presided over Venezuela, Gran Colombia, and Ecuador, the last of which qualifies him for this.
Catherine the Great of Russia was born in Germany (Prussia).
Chiang Kai-shek, president of Taiwan, was born in Xikou, mainland China.
England’s William the Conqueror, of course, was born in France.
Every Pakistani President or PM until Benezir Bhutto was born before there was a Pakistan.
Brezhnev was born in Kamenskoye (now Dniprodzerzhynsk in Ukraine), his ethnicity was specified as Ukrainian in some documents and Russian in others.
Augustus Henry Fitzroy, 3rd Duke of Grafton and the tenth British Prime Minister was born, but nobody knows where.
George II was born at Schloss Herrenhausen, Hanover, Germany, William III was born in The Hague, Netherlands, and many British Monarchs were born in France.
Israel is a special case. Benjamin Netanyahu is the *only *Israeli Prime Minister to be born in Israel; four previous Prime Ministers (Rabin, Sharon, Barak and Olmert) were born in the country that would be Israel in the future; while all other Prime Ministers (including every one prior to 1975) were born in various European countries.
Many English monarchs between the Norman Conquest and the Tudors were born in France, because the Norman and Planatagenet lands included parts of what is now France. I don’t think many, if any, Scottish monarchs were born outside Scotland.
George II was the last British monarch not born in Britain. Numbers of politicians born outside the UK have made it into Parliament, but the only one who became Prime Minister was Andrew Bonar Law, who was born in Canada (there were some eighteenth century ministers born in Ireland, but that was part of the UK then - and citizens of Commonwealth countries are entitled to vote and stand for election in the UK if they live here; the New Zealander Bryan Gould was at one time a contender for the Labour Party leadership).
Surprising. The first generation born after '48 must be in their late 60’s by now, so one would have expected more than just Bibi.
When I lived in Ecuador in the early 90s, the president, Sixto Durán, was a man who had been born in Boston.
Bibi’s been in office for a long time, and he just came in under the wire - born in 1949.
Besides, of the past four PMs, two were roughly his age (Olmert - 1945, Barak - 1942). Ariel Sharon was the outlier, having been born in 1928 and was largely considered a has-been when he was elected in 2001. Remember, he was seen as a “caretaker” Likud leader at the time, and his election came as a surprise to everyone.
King Bhumibol of Thailand was born in Cambridge, Massachusetts.
The 1st Duke of Wellington was born in Ireland in 1769, when it was a separate, although British-dominated, country.
Andrew Bonar-Law, as mentioned, was born in New Brunswick.
Soviet records indicate that Kim Jong-Il, the second leader of North Korea, was born in Russia.
However, his official biography claims he was born in Korea - on a sacred mountain, no less.
You know who else was not born in the nation they led? 
mentioned int he OP, I know, but I had to get that in…
As for the US, it would have been possible for a foreign born person to be president in the early days of the republic, but not now.
What country was he the leader of? 