OK- summer looks out- how about early April (at this time- I suspect late April or May might be better).
Looking at the 3 day train ride from Perth to Adelaide, then most of the rest of the time outside the Melbourne area, staying at a B&B or such and exploring out from there by car.
You guys better learn to drive on the right side of the road by the time we get there.....