I was wondering about this, given that on the one hand it's considered a mandatory religious duty, but on the other, such a journey from somewhere like Indonesia or West Africa in pre-modern times would have been a lengthy, dangerous and expensive task, surely beyond the ability of the average peasant farmer?
If there were areas where the Hajj was not undertaken, how did the inhabitants deal with that? Were there ever "alternative pilgrimages" to a more accessible holy site?
TL;DR: You are correct, most Muslims did not go to Mecca (at least in Southeast Asia). They did, however, greatly respect those who did.
You know the Ottoman sultans? The Commanders of the Faithful, Successors of the Prophet, Protectors of the Holy Places, and all that jeez? Theoretically the Caliphs of Islam for four hundred years?
Just one Ottoman sultan - out of the thirty-six who ruled the empire - ever went to Mecca. That one sultan was Selim the Grim, the very man who conquered the Holy Land for the empire. As this example suggests, the obligation of the hajj was frequently ignored even by the most powerful Muslims in the world, never mind a peasant in Java or Nigeria.
Indeed, the hajj is generally not considered obligatory for those who lack the means to go, so Muslim peasants wouldn't have felt they were committing a grave sin by not going in the first place. From Qur'an 3:97 (emphasis mine, Abdel Haleem translation):
Pilgrimage to the House is a duty owed to God by people who are able to undertake it.
So there wasn't really a pressing need for dirt-poor peasants to "deal with" not being able to go on hajj; they didn't really have to, even if they would like to (Islam frowns on going into debt to pay for pilgrimage, even if this did commonly happen).
And this answers your other question. While every corner of the Islamic world is stocked with pilgrimage sites, they weren't really conceived as "alternative pilgrimages" for people who couldn't go to Mecca any more than the Camino de Santiago is an alternative pilgrimage for people who can't go to Jerusalem. Case in point; thousands of pilgrims still cluster around the tombs of Al-'Aydarus in Aden, Rumi in Konya, or Tuanta Salimaka in Makassar, even though most of these pilgrims could probably go to Mecca if they wanted to thanks to modern technology.
Now, let's have a closer look at the very place you mention in your title: Indonesia.
Indonesians have gone on hajj for at least five hundred years. The earliest example I know of is from a Malay chronicle dated to 1371, featuring a ruler "requesting permission to go on hajj to his son and to all the viziers and ministers." Another notable pilgrim was the 16th-century Sufi poet Hamzah Fansuri, often considered the founder of modern Malay verse. Fansuri's tomb - dated to 1527 - has recently been found in the holy city.
But generally speaking, the hajj was a heavy economic burden even for the richest Indonesian aristocrats. To give an example, in the early 19th century Raja Ahmad, a diplomat and chancellor hired by many Malay sultans, wanted to travel to Mecca. Despite being one of the most influential personages in the Malay world, he was unable to cover the expenses on his own and had to raise money in various royal courts. He did not go on hajj until he had accumulated $14,000, in an era when the average agricultural laborer in Singapore might make $50 every year. And although Raja Ahmad was from Riau, the most powerful of all Malay kingdoms, we know that he was the very first Riauan to ever make the hajj.
Of course, Raja Ahmad was less like your average hajji today and more like those UAE oil magnates who come to Mecca on private planes. The raja spent lavishly once in Mecca, buying land and purchasing three houses just so he could give them to his guides and buying land to donate to a local hospice. What about the average person?
In the year 1850, the number of hajji departures from Java was a grand total of forty-eight, out of a total Javanese-speaking population of 9.5 million. By the 1890s, advances in ships and transportation made the hajj far easier and more widely available. But even in British Malaya in 1896, you needed hundreds of Straits dollars to make the hajj; the basic rituals of the pilgrimage took around $300, not to mention the costs of a month-long trip across the Indian Ocean and the possibility of staying for much longer in Arabia (voluntarily or otherwise). Again, recall that in the mid-19th century the average laborer in Singapore was making about $50 per year. As late as the 1930s, some years there were less than 100 pilgrims going to Mecca from British Malaya!
So the hajj was an impossibility to the majority of Southeast Asian Muslims.
And, some would have said, you didn't need to go to hajj. These perspectives are particularly common in the first centuries of Islamization. The sultan of the 15th-century kingdom of Melaka proclaimed that the pilgrimage to Mecca was no longer obligatory, since "Melaka was to be made into [a second] Mecca."^1 A certain rejection of the hajj is corroborated by other sources. One Javanese chronicle says that two early Muslim proselytizers in Java wished to go to Mecca. But first they went to Melaka, where they received advanced training in the faith from a local pandit. This pandit finally convinced the two Javanese that they should not perform the pilgrimage and instead return to their homeland to spread the faith.^2 The Sufi poet mentioned earlier, Hamzah Fansuri, also seems to have an ambiguous attitude towards the spiritual benefits of pilgrimage. God is not in Mecca, but within you. Or at least, this is what one of his poems suggests (translation from The Poems of Hamzah Fansuri):
Hamzah Fansuri di dalam Makkah
Mencari Tuhan di bayt al-Ka'bah,
Di Barus ke Kudus terlalu payah
Akhirnya dapat di dalam rumah.
--
Hamzah Fansuri in Mecca
Sought the Lord at the Shrine of Ka'bah
[Yet] at Barus it was too much trouble to go to Jerusalem
[For] eventually he found Him in his own house
But these unorthodox opinions were those of a distinct minority, especially as time passed. It is safe to say that by the 18th century, the hajj was a major part of Muslim consciousness in Southeast Asia. Rulers went on hajj to bolster their legitimacy; one sultan in Java went to Mecca twice before his accession as ruler, so he simply took the title of "Sultan Hajji" to drive home the fact that he, unlike so many others in Southeast Asia, had carried out the final Pillar of Islam. For similar reasons, other rulers around Southeast Asia tried to go on hajj (although it was almost always politically impossible to do so) or at least send emissaries to represent them in the Holy City.
Why? As I discuss extensively here, Islam became closely associated with royal authority for Southeast Asians. The pilgrimage, then, was a means of raising a ruler's prestige and hence his support base in a highly volatile political environment. As one historian says of Sultan Hajji:
Undertaking the Hajj cost him money, of course, but he recouped those funds in increasing the number of followers available to him as a result of his raised status as a successful pilgrim.
Even if you were not a ruler, you would be treated very differently once you returned from hajj. In the 19th century, an anonymous orthodox Muslim complained bitterly about the Javanese belief that dead pilgrims from Mecca could rise from the grave, or that hajjis could bring fortune and lengthen the lives of their followers. In other words, pilgrimage to Mecca greatly augmented the supernatural Islamic powers that people with authority were considered to imbibe. No wonder there were problems with fake hajjis.
Meanwhile, increasing integration of Southeast Asia into pan-Islamic networks of theological and cultural exchange made the importance of the hajj increasingly prominent. In the early Islamic Malay poem The Epic of Hang Tuah, the hero Hang Tuah goes to Mecca almost as an afterthought after arriving in the Middle East for political purposes. This isn't an exception; the hajj is relatively inconspicuous in early Southeast Asian texts. But by the 19th century, even peasants were saving for decades to go to Mecca.
Whenever people go on pilgrimage, they will some day return - but they seldom return alone and unchanged. As more and more Southeast Asians went to hajj, Mecca became an increasing influence in the archipelago. Already by the 18th century Javanese princes were receiving war banners from Mecca with letters such as the following:
The reason why this banner has been sent to you is that we in Mecca have heard that Your Highness, being a truly princely leader, is much feared in battle. Value it and make use of it, please God, in exterminating your enemies and all unbelievers. Good wishes and greetings are conveyed to Your Highness on behalf of the old God-fearing people of Mecca and Medina.
The next century, pilgrims from a Mecca that had just been taken over by Wahhabism would bring the new sect - and their characteristic fundamentalist carnage - with them. This was perhaps the first genuinely Islamist movement in Indonesia.
So, just as more and more Southeast Asians left their imprint in Mecca, Mecca cast a shadow on Southeast Asia that grew ever longer.
^1 Milner, "Islam and Malay Kingship," p. 30
^2 Reis Thomaz, "The Malay Sultanate of Melaka," p. 89
Most of this discussion follows Eric Tagliacozzo's The Longest Journey: Southeast Asians and the Pilgrimage to Mecca.