Saw an area I really liked the look of in outback Queensland part way between Winton and Boulia a few years back, but at 150km from the nearest town and 1400km from Brisbane, I don't think it's going to get used any time soon.
There's some great sandstone terrain around Kalumburu too, but I hear the access road's a bit dodgy.
As for your trip, I don't think I've heard of one as epic as that since Jenny and Susanne's trip to Europe in 2011 (and they at least had a volcano to blame).
It looks like great orienteering terrain the whole way from Mt Isa to Cloncurry. Pity Mt Isa is so hard to get to, and nearly impossible to leave.