31 days in Indonesia

==Schedule==
Traveling in Java and Bali is pretty easy... by Indonesian standard. You could add the Gili and Lombok, Komodo will be very difficult. You definitly have to skip Borneo.

Plan B: land in Java,fly to Borneo. Stay one month there.

Plan to come back for your plane at least 2 days in advance. You never know.

==Nature==
Java (1000 pl/km2) and to some extend Bali, are MASSIVELY overcrowded islands. If you can see wild life there, it means you are in a severely endangered area and should not, ethically, be there.

However, there are wonderfull lanscapes in the Montains (Bali,Lombok and East Java). And temples, of course. Muslim Indonesian are (usually) very proud of their Indu heritage (or Boudist for Borobudur)

Orang Utan sighting in Borneo is often, but less obviously, objectionable. Try to avoid those who are "sure" to see Orang Utan as it is more likely tamed animals.

Traveling by boat in Kalimantan(Borneo) forest is something I deeply regret I haven't done. It must be marvelous. Even if it is difficult to find "honest" Orang Utan, you'll get the (remaining) trees crocodiles, python and so on.

== Traveling ==
I totally approve you traveling by trains, buses and boats. But after tasting the Indonesian roads, you'll need more than 1 day of rest.
By the way, road traveling in Java will provide little landscape, but you'll meet nice people.

You should also try to learn a bit of Indonesian before you arrive. It is fairly easy and definitely useful.
If not,train patience before departure. Unless you travel with a guide, you'll be very often stuck by puny details.

Disclaimer: Never been to Indonesia, but planning to go in August+September. There are some quite detailed questions I can't answer, but I think there is one rather big issue you should consider before thinking about the others:

The Islamic month of fasting, Ramadan is from June, 18th to July, 16th this year. Observant Muslims are not allowed to eat from sun rise to sun set. One of the most important Indonesian holidays, Lebaran or Eid al-Fitr, follows directly after Ramadan. It officially last for two days, but usually the government declares some more days around them to be general public holidays. A lot of people use this holiday to visit family & friends or to vacation themselves.

In a densely populated area like Java with not-quite-optimal transportation infrastructure this necessarily means high congestion on roads, over-booked public transport and higher accommodation prices. From what I have heard, public transportation is often booked out weeks in advance.

I heard of one additional annoyance: Observant Muslims have to pray more often and also earlier in the mornings during Ramadan. This means that you might hear the muezzin performing his call for prayer more often, very early in the morning (well before sun rise) and louder than during the rest of the year.

The religious laws are not enforced as strictly as in more conservative countries (except for possibly Aceh). This means that as a Westerner/non-Muslim you shouldn't have problems to get food during the day.

Note that since Indonesia is such a huge and diverse country, the issues I outlined might be a major problem in some areas (Aceh, the most conservative province; Java, since it's so densely populated) while they aren't affecting you much at all in others (Bali is mostly hinduistic).

So all in all, traveling around Java in July without booking in advance and being very flexible might not be a good idea. One idea is to turn your planned route around so that you'll be in Java after Lebaran.

For the rest of your questions, it mostly depends on what you want to do/how you want to travel.

Is it realistic (or too much/little) for 31 days? should we also go to Rinca Island?

Certainly not too little, for my feeling. Don't forget that distances are quite long (at least for me, being from tiny Austria ;) ) and you'll need time to get around. Personally, I'd condense the itinerary a bit: For both Rinca and Komodo island, the main attraction are the dragons. If there isn't a good reason to go to both of them, I'd rather spend a day more at one of them.

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?

I usually like to pre-book for a few corner stones of my itinerary and then fill in the gaps on the go; This way you get some flexibility and avoid having to spend too much time looking for transport and accommodation that could otherwise be spend exploring or on a nice beach.