16日あれば大陸東半分を陸路で半周できます。

ケアンズからブリスベン、シドニー(経由のみ)はバス。あとは列車でキャンベラ、ブルーマウンテン、アデレード、メルボルン、アデレード、アリススプリングス、ツアーでウルル往復。バスでケアンズがいいかと。
鉄道パスは約4万円です。
NSW州の鉄道パス(2万ほど)も日本で買うとブリスベンから利用でき、シドニー～メルボルンも使えるので、アデレード～メルボルンは片道でOKです。

宿はYHが最適かと。
http://www.jyh.or.jp/