When you plan to head thru Brisbane to Fraser, make sure you give Shonky and myself a call. We'll gladly have a drink with the grand-pooh-bah/guru/messiah himself and his better half.
For renting a 4x4, there are a number of places in brisbane and maryborough but it's 250+ k from brisbane to Hervey Bay (ferry to Fraser) so you may like to hire something a little closer. where are you staying on fraser? Kingfisher resort is excellent, spent the y2k new year there. there are 4wd on the island to hire, they're very utilitarian and cost nearly $100 day (30 quid) plus fuel. Don't know how much the car barge is tho.

Fraser is probably the only place you'll need a 4x4, we've had sealed roads and electricity for some time now. You may prefer to get a campervan/winnebago thing. Bigger to drive but you can stop nearly anywhere. Useful on long drives. (2000K Melbourne to Brisbane)

I'll get some more info on stuff soon.