Disclaimer: Nunca esteve na Indonésia, mas planejando ir em agosto + setembro. Há algumas perguntas bem detalhadas que não posso responder, mas acho que há uma questão bastante grande que você deve considerar antes de pensar nas outras:
O mês islâmico de jejum, o Ramadã é de 18 a 16 de julho deste ano. Os muçulmanos observadores não podem comer desde o nascer do sol até o pôr do sol. Um dos mais importantes feriados indonésios, Lebaran ou Eid al-Fitr, segue logo após o Ramadã. Ele oficialmente dura dois dias, mas geralmente o governo declara mais alguns dias ao redor deles para ser feriados gerais. Muitas pessoas usam esse feriado para visitar a família & amigos ou para férias.
Em uma área densamente povoada como Java, com infra-estrutura de transporte não muito boa, isso significa necessariamente alto congestionamento nas estradas, excesso de transporte público e preços mais altos de acomodação. Pelo que tenho ouvido, o transporte público é muitas vezes reservado com semanas de antecedência.
Ouvi falar de um aborrecimento adicional: os muçulmanos observadores precisam orar com mais frequência e também no início da manhã, durante o Ramadã. Isso significa que você pode ouvir o muezim realizando sua chamada para orar com mais frequência, bem cedo pela manhã (bem antes do nascer do sol) e mais alto do que durante o resto do ano.
As leis religiosas não são aplicadas tão estritamente como nos países mais conservadores (exceto possivelmente com Aceh). Isso significa que, como um ocidental / não-muçulmano, você não deve ter problemas para conseguir comida durante o dia.
Observe que, como a Indonésia é um país tão grande e diversificado, os problemas que delineei podem ser um grande problema em algumas áreas (Aceh, a província mais conservadora; Java, já que é tão densamente povoada), enquanto eles não afetam você. muito em todos os outros (Bali é principalmente hinduísta).
Então, no geral, viajar por Java em julho sem reservar com antecedência e ser muito flexível pode não ser uma boa ideia. Uma ideia é transformar sua rota planejada de modo que você seja em Java depois do Lebaran.
Para o resto das suas perguntas, depende principalmente do que você quer fazer / como você quer viajar.
Is it realistic (or too much/little) for 31 days?
should we also go to Rinca Island?
Certamente não é muito pouco para o meu sentimento. Não se esqueça que as distâncias são muito longas (pelo menos para mim, sendo da pequena Áustria;)) e você precisará de tempo para se locomover. Pessoalmente, eu condensaria o itinerário um pouco: Para ambas as ilhas Rinca e Komodo, a principal atração são os dragões. Se não houver um bom motivo para ir a ambos, prefiro passar mais um dia em um deles.
Is it fine to not book anything beforehand? We wanted to take it as we go (in case we change plans underway). Or is it required to prebook some tours or hotels?
Eu geralmente gosto de pré-reservar algumas pedras do meu itinerário e depois preencher as lacunas em qualquer lugar; Dessa forma, você obtém alguma flexibilidade e evita gastar muito tempo procurando transporte e acomodações que poderiam ser exploradas ou em uma bela praia.