I'm an Aussie (NSW based) in London but i'm in Melbourne for my brother's wedding last night. At the reception I was talking to a bloke living in Melb that was interested in freediving (wasn't you by chance was it??), so there's definitely enough interest down here to get some guys training. I would suggest getting in touch with the Australian Freediving Association on
www.ozfreediving.com/afa or go to the Australian Freediving Community website on
www.ozfreediving.com and look in the VIC section.
Cheers,
Ben