I'm going to assume that here you're mostly interested in "immediately before the founding of the Safavid Empire," i.e., ~1500 CE, and ignore places like North Africa (which was a historical center of Shiʿism under the Fatimids, but by this time those days were long past). The areas you should be most interested in, then, are those in the Arab world (in particular, modern Lebanon, Iraq, and Bahrain). But while I hope that I'll address your question, think about what it means for an area to be majority Shi'i in the first place: is it enough for a village to be? a city? How wide an area are you looking for, exactly? (Generally speaking, significant Shiʿi schools will attract a significant Shiʿi population, but as you realize this may not always extend beyond the immediate neighborhood of the school.)

Interestingly, the two areas you named—Northern Iran and Azerbaijan—were only arguably Shiʿi before the mid-sixteenth century. Like the Safavid Empire's founder, Shah Ismaʿil I, the most prominent tribes inhabiting this area were Qizilbash ("red-heads," referring to their distinctive red headwear), a sect marked by fanatical devotion to the head of the Safavi Sufi order and to the family of ʿAli. Now, while today we would immediately associate that second part with Shiʿism, at this time it was quite normal for Sunnis and other non-Shiʿi sects to profess their admiration for ʿAli and his descendants. I talk a bit about this "confessional ambiguity" and the case of the Alevis (descendants of the Anatolian Qizilbash who remained under Ottoman rule) here. The Qizilbash weren't unique in this regard—the late fifteenth century saw a proliferation of often-messianic sects that straddled the line between Sunnism, Shiʿism, and ghulāt (positions deemed too extreme, and potentially downright un-Islamic, by both groups). The important element that Ismaʿil introduced, and which marked his firm break with the Sunni world, was the compulsory curse (tabarraʾ) upon the first three historical caliphs.

The dominant religious denomination in modern Iran, however, is not the Qizilbash sect—it is Imami, or Twelver, Shiʿism. (I talk a bit about the differences between the two here.) The conversion of the Iranian people (and, to a more limited extent, the Safavid monarchs) from Qizilbash religion to Imami Shiʿism is a long and complicated story, but the essential part for answering your question is that it was not an indigenous movement; rather, the process relied on a population of clerics imported from the Arab world. Of these, the most prominent by far were those from the region of Jabal ʿAmil in southern Lebanon, collectively known as the "ʿAmili" clerics. The importation of these foreign clerics with their erudite and codified Shiʿism may have been a move to undercut the predominantly Sunni cities of Iran, who were not impressed by the relatively unintellectual Qizilbash faith—but it also undercut the religious authority of the Safavids themselves, whose position as heads of the Safavi order was not recognized under the new dispensation.

While Jabal ʿAmil was particularly important in the context of Safavid history, we should also mention the significant Imami Shiʿi populations in Iraq (where the pilgrimage sites of Najaf and Karbala attracted newcomers as well as maintaining the prior population), Bahrain (conquered by the Shiʿites of Hormuz in the early fourteenth century), and other areas of Eastern Arabia. Yemen was, and still his, home to an entirely distinct Shiʿi sect, the Zaydis (or "Fivers").

Finally, I should briefly mention the Shiʿi states founded in the early sixteenth-century Deccan. Some caveats here: first, as was generally the rule in Muslim India, Muslims of any sort were often the minority even in officially-Shiʿi states. Second, even the earliest of these officially Shiʿi states, the ʿAdil-Shahis of Bijapur, only proclaimed Shiʿism as the official religion in 1502 after hearing about the Safavid victories (a second Shiʿi kingdom would be established at Golconda under the Qutb-Shahis in 1512), so in neither case was this "before the founding of the Safavid Empire." (Though prominent individual Shiʿites are attested in the history of the region prior to this point, so it's not like the development came out of nowhere.) Thirdly, I should stress that both of these Deccan dynasties were ultimately of Iranian or Caucasian origin, and continued to draw an immigrant population from Iran—so these aren't examples of a particularly concentrated Shiʿi population in the Deccan (again, the Arab examples are probably more to your point there) so much as they are signs of the wide geographical reach of Imami Shiʿism at the beginning of the sixteenth century.

FURTHER READING

Iran: On the Safavids' importation of and relationship with the ʿAmili clerics, see (in addition to her article on Jabal ʿAmil, linked above) Rula Jurdi Abisaab, Converting Persia: Power and Religion in the Safavid Empire [WorldCat]. On the cursing of the first three caliphs, see Rosemary Stanfield-Johnson, "The tabarraʾiyan and the early Safavids" [Iranian Studies]. (On the ghulāt and other Iranian religious heterodoxy, see S. A. Arjomand, "Religious Extremism (ghuluww): Sufism and Sunnism in Safavid Iran: 1501-1722" [JSTOR], but this is rather dated and should only be used as a springboard to further research; see Shahzad Bashir, Messianic Hopes and Mystical Visions [WorldCat] for a more focused but far better-regarded account of one such sect.)

Arabia: A good, if very broad and by now somewhat dated, overview of Arabian Shiʿism can be found in Juan Cole, "Rival Empires of Trade and Imami Shiism in Eastern Arabia, 1300-1800" [JSTOR].

India: Umar Khalidi, "The Shiʿites of the Deccan: An Introduction" [JSTOR]. On the continuing relationship between Iran and the Shiʿi sultanates, see Keelan Overton, ed., Iran and the Deccan: Persianate Art, Culture, and Talent in Circulation, 1400-1700 [WorldCat].