What sovereign Jewish polities have existed outside of Palestine?

One could make the case that the Jews of Spain-(from the collapse of the Roman Empire, until the arrival of the Moors or from around 476 CE, until 711 CE), had a quasi or semi-autonomous polity in Southern Spain.

It is not exactly known as to when the Jews arrived in Spain. There is speculation that the Jews lived in Spain since the beginning of The Roman Empire. If this historical timeline is accurate (or close to accurate), then the Jewish presence in Spain existed for over 1500 years.

There were Jewish communities throughout Spain proper, in cities, such as Barcino/(the original Roman name for, "Barcelona"), Toledo, Cordoba and Seville. Regions, such as Andalusia, Valencia and Castile, had sizable Jewish populations for centuries.

When Roman Spain collapsed, there were 2 subsequent powers who filled its political vacuum, the Byzantines-(who ruled the coast) and the Visigoths-(who settled and ruled from Barcelona, to Castile). However, there were parts of early, pre-Islamic Medieval Spain which were somewhat autonomous. Areas, such as the majority of Northern Spain, as well as Southern Spain/Andalusia, were essentially independent regions. The Celts had a presence in a sizable part of Northern Spain during this time, though had a limited presence-(along with the Visigoths), in Andalusia.

However, the Jewish presence in Andalusia was fairly widespread, when compared with other Spanish regions. This of course does not automatically prove that there was an independent or quasi-independent Jewish national polity in Southern Spain during the first half of the early middle ages. Though it does suggest that the Jews of Andalusia, during this fairly short time in History, may have had more regional autonomy and self-governance, than when compared with other Spanish regions that were controlled by Visigoths, Byzantines or Celts. Of course this would all change with the invasion of the Muslim Moors in 711 CE and an Iberian Caliphate would be established for the next 800 years.

Arthur Zuckerman wrote a book prosposing that there was an independent Jewish Kingdom in Medieval France. When Pepin the short campaigned against the Moors, the city of Narbonne offered resistance to him. The siege lasted for years and finally he sent them offers. They would only agree to having their own prince. There was a large Jewish population in the city and they send for a legitimate leader, the Exilarch himself or a descendant of David. Makhir, the Nasi or Prince, may have been the Exilarch. A lot of the history is recreated from Carolingian records. He also claims from epics that Makhir married Charlemagne's aunt, Adla. The kingdom lasted for about as long as the Carolingians did, and served an important defensive role in the south. What we definitely know, is that there was a renowned academy which Makhir started at Narbonne. The Jews had thriving communities at Narbonne and Toulouse and had a great deal of autonomy. Officially, it is just considered to be a Visigothic subject of Charlemagne.

If you want to know what my answer should have looked like, read this: Jewish King of Narbonne

Adiebene the beginning of the common era.

Adiabenian rulers converted to Judaism from paganism in the 1st century. Wikipedia quoting Gottheil, Richard. "Adiabene". Jewish Encyclopedia. Retrieved 8 November 2011.

In Babylonia there was a short lived parthian client state run by two Jewish bandit brothers.

The Khazars in what is now Southern Russia and Ukraine converted to Judaism in the 8th century.

• The Himyarite Kingdom in Yemen, which was ruled by a converted tribal warlord as a Jewish state in for a brief period in the early 6th century.
• According to oral tradition, the Kingdom of Semien in Ethiopia was ruled by a Jewish dynasty that claimed descent from the high priests of David and Solomon. Its golden age was 400 years from around 850-1270 AD, though some traditions maintain there was an independent Jewish "Kingdom of Beta Israel" from the 4th Century AD. It was destroyed by the Ethiopian Empire in 1627. The Encyclopaedia Judaica offers a considerably more skeptical take on the Beta Israel historical tradition. The authors note that while the Semien region of Ethiopia undoubtedly has a large Jewish influence, there are very few reliable sources for the 6th century - 13th century that can establish the existence of an autonomous kingdom with Jewish rulers. The authors acknowledge that from 1270-1632 the Beta Israel had some autonomy and warred with the Ethiopian Emperor, but they seem to stop short of recognizing Beta Israel as an autonomous kingdom.
• The Jewish exilarch Mar Zutra, sometime in the 6th century, created an independent Jewish kingdom (in Mahoza, southern Iraq) that lasted for seven years.
• The Khazars in what is now Southern Russia and Ukraine converted to Judaism in the 8th century.
  • Josephus reports (Ant., 18:314ff.) that two Jewish brothers, Anilaeus and Asinaeus (Ḥanilai, Ḥasinai) established a "Jewish state" in Babylonia, which lasted from about 20 to about 35 C.E. (source).