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.