From personal experience there are some great skies south of Darwin in July.
I agree with Joe's comment about Katherine Gorge: I led a canoe trip with about 20 teenagers up the gorge many years ago, and I remember camping on an island in the river under the stars. The sky was mind-blowing!
Arkaroola in SA (on your list) has fabulous skies (SQM usually better than 21.8 and often sub arc-second viewing), as well as observatories and telescopes that you can hire. Doug Sprigg (the owner) is very generous with his time and equipment for visiting astronomers. However, it is a long way from anywhere, and it gets very cold at night in July!
If you are going to Cairns it would be worth contacting Ian Maclean, who runs an Astronomy shop, a portable planetarium, and astronomy tours. He has a dark sky site west of Cairns also. See:
http://www.nightskysecrets.com.au/news/tours/
(If you are planning to see the lava tubes as well, then this might be your best bet as the Undara lava tubes are about 2 1/2 hours drive south-west of Ian's dark sky site, which is just east of Mareeba.)
All the best, and enjoy your trip!
- Dean