I went on a road trip some years ago and it took me 13 months to get out of Queensland
I was only using my example as a way of saying there is so much to do in Queensland.If diving is your focus, I'd fly between major destinations.
And I agree, flying to major destinations is the way to go and hire a car to get around [just remember to drive on the other side of the road].