I think you'd only need a 4 wheel drive if you were planning to do some fairly remote camping. From memory you really need one for Kakadu, and some of the less well travelled places around Alice Springs / Uluru.
Personally, I would either fly in to Uluru, and spend only a day or two there, or take a couple of weeks with a 4WD around there and Alice Springs. Given that you have a month for the whole country, the latter option seems a bit unlikely.
There are lots of decent surf beaches along the Great Ocean Road. You might find the water is a lot colder than Brisbane! Do you like penguins? There is at least one good penguin beach near Port Campbell.
Look me up when y ou're in Melbourne, too! I've actually never met PaulWay which seems a little silly. I'm sure we'll be able to organise something.
I don't know what you're doing for accommodation, and I doubt that Lord Empeg is particularly pressed for cash, but I have a spare room if you want it.
Richard.