In terms of a country that is roughly analogous to OTL Indonesia, unlikely before the late 19th century. The Republic of Indonesia as a (supposedly) equal union between all the people of the former DEI is quite a specific distillation of the potential states that could have emerged from Dutch Imperialism. It required a good century of common experiences and ethnic/cultural intermixing in order to create that sense of identity. Obviously, in Aceh and West Papua, and a few other places, this identity ranged from weak to non-existent which is unsurprising given the rather divergent experiences these regions had compared to the Javanese/other Sumatran core. IMO an Indonesia that gained independence peacefully even in OTL would be unlikely to include those areas.
In terms of what is just the core region of Java/non-Acehnese Sumatra, IMO it's possible for a secular republic to emerge sometime after 1850 or so. Modern technology mutes the problems that previous archipelagic entities such as Srijaya and Majapahit had in maintaining basic centralised control, while ideas of nationalism slowly began to penetrate the urban centres around this time. The biggest variable, IMO, for an early independent Indonesia (other than 'how do they kick the Dutch out') is the disposition of the Eurasian/Indo population, who formed a huge percentage of the educated non-Dutch. If they support an independent state it is probably viable quite early, so long as that state has the support/patronage of a Great Power. Without them, the skills for running an economy that is so integrated with the rest of the world probably don't exist until the early 20th century.
So for an actual scenario, IMO the easiest way to achieve this would be a hostile takeover of the Netherlands themselves, perhaps by Germany, sometime during the 19th century which leaves the Dutch colonies unconquered but obviously unviable on their own without a metropole. This could certainly lead to another European power outright taking control of them, but as was seen in places like Egypt and Morocco it was possible for the imperialists to allow for some degree of local autonomy. Perhaps a Dutch government-in-exile that is essentially supported by the Eurasian/Indo population which gradually 'goes native' as the Indos take control through sheer numbers which also sees the Indonesian aristocracies regain some real power. This could eventually lead to a fully-formed independent state very early in the 20th century, with the right variations in North Atlantic power structures. The biggest hurdle is finding a reason for the Netherlands to be conquered during the time of the Concert of Europe...
