ホリデーアパートメントなら・・

下記のHPで検索してみてください。いろいろあります。大分前ですが、私はcityのスタジオタイプのキッチン付ツインで1週間、500ドル位で泊まれました。場所的にはメルボルン市内中心か、セントキルダ、サウスヤラ辺りがいいと思います。

http://www.ratestogo.com

http://www.challenge.jp/cities/view/3