what about websites of local clubs or groups that might have a buy and sell section. You might be able to get something suitable second hand for significantly less. (I'm just a student so I need to be pretty cheap - that's all).
. Up here, there is all manner of stuff from clothes/wheels/shoes etc for sale. From the cycling clubs/triathlon clubs/veterans clubs, off road clubs etc.
I bought 2nd hand spd pedals and cleats for $30 and shoes in virtually brand new condition from an op shop for $5.
I know that was a fluke!
but that's an avenue you might be able to look at.
As for bike shops to help you, I wouldn't really know what's in Melbourne yet.
I know I'm not much help but hey, I try!