What significant regions and countries became Muslim without being first conquered by a Muslim power?

The Ghana Empire became Muslim in the 1100's. The subsequent fall of the Ghana Empire and the rise of Islam coincided perfectly. Arab tradition states that the Muslim Almoravids conquered Ghana. While this probably isn't true, there was likely an element of political control involved in maintaining the gold trade. They did invade several times as far as Mali. Moreso, it was the dynastic struggles that the Almoravids encouraged led to the downfall of Ghana, and the rise of Mali. Mali was Muslim and furthered the Islamization of the region.

The Kanem Empire covered a north-south trade route through the middle of the Sahara desert. It began around 700 A.D. and was never invaded by a Muslim power. A dynastic change occured in 1086 and the new king was a convert to Islam. This caused a rift in the society, which would become a recurrent theme in the history of Chad. Today it is 55% Muslim.

The Malacca Sultanate developed on the heels of Singapura. Singapura had become very rich during the Pax Mongolica period, arousing the concern of its neighbors. They overran it and continued to threaten the area. A new port was created up the coast which became a safe haven for merchants, and became the core of the Malacca Sultanate. The leaders were Islamic from an early time.

The sultanate controlled the Malacca straits. When the Champa-Vietnamese war led to the decline of Champa around 1471, Malacca's influence led to the growth of Islam along the Vietnamese coastline. This was the high point of the Sultanate, after which it was invaded by the Portugese.

The Volga Bulgars converted to Islam in 922 A.D. They tried to convert Vladimir I of Kiev without success. Their capitol was Bolghar on the Middle Volga. It was a major center of Eurasian trade in the crusade period. In the later Mongolian period, Bolghar grew exponentially.

The Golden Horde was a Mongolian and Turkic Khaganate in Russia that was independent for most of its existence. Berke Khan, the second Khan who ruled only the western half, converted to Islam around 1240. His conversion was due to his alliance with the Mamluks in Cairo against the Mongolian Ilkhanate in Persia. Widespread Islamization occured in the 14th century, after the conversion of Uzbeg Khan in 1313. The period of Uzbeg was the high point for the Horde. One reason for his conversion to Islam was to remove the influence of eastern Mongolians and Buddhists. The Golden Horde was located in the Transcaucasus, which was an important Trans-Caspian trade route.

As a nuance, the Umayyads had invaded the Transcaucasus 737. They forced the Khazar Khagan to convert to Islam. This was superficial and the Khazars ignored them afterwards.

Islamic merchants had a presence in all of these places since the early Islamic period. The work of the Sufi Orders from about the 10th century made Islam a majority religion in the Middle East, then proceeded to spread it to the extremities of southeast Asia and Africa.

Thanks to Alex for pointing out that the Golden Horde became Muslim.

Many of the descendants of the Mongol empire (except China, Mongolia and Far East). It is true that they were conquered by the Mongols, but at that time Mongols were not Muslims. At a later period some descendants of Mongols converted to Islam, in fact they accepted the religion of one of the conquered nations, and the result is that their contemporary descendants are Muslims. This includes Tatars, for example, and several peoples of North Caucasus region (Chechnya, for example). Modern Tatars and Chechens are mostly Muslim.

They are descendants of the state which was called Ulus Joshi, or later the Golden Horde, whose Mongolian rulers converted to Islam (Uzbeg khan, in 1313) and eventually made Islam the dominant religion without being conquered by an Islamic state. Eventually this Golden Horde dissolved into pieces and most pieces were conquered by the Christian Moscovia. But their population remained mainly Muslim and remains to this day.

Modern Mongolia has only 3% Muslims, according to Wikipedia.

States in West Africa, including Senegal, Gambia, Guinea, Burkina Faso, Niger, Mali and Nigeria

The conversion to Islam in this region happened in a gradual process. Margari Hill's The Spread of Islam in West Africa: Containment, Mixing, and Reform from the Eighth to the Twentieth Century described the process in three stages, which doesn't include invasions:

1. Arrival of Muslim merchants and scholars who were welcomed but segregated by the African rulers (from 8th century)
2. African rulers began to adopt Islam, initially ruling over largely non-Muslim populations. But the populations gradually began to adopt Islam, "often selectively appropriating aspects of the faith" (from 13th century)
3. Various movements and "jihads" which had the result of increased Islamic orthodoxy and less mixing with pre-Islamic practices (from 19th century)

For sure the classification into these stages is simplified, but they give the rough idea. In addition, in the late 11th/early 12th, there were incursions by the North African Almoravid dynasty, who captured a few settlements and attempted to spread Islam, but this dynasty was nowhere near "conquering" West Africa.

Reference:

• Margari Hill (2009), The Spread of Islam in West Africa: Containment, Mixing, and Reform from the Eighth to the Twentieth Century, The Stanford Program on International and Cross-Cultural Education