マレーシア航空でいいのでは？

こんばんは

マレーシア航空利用でもワールドパークスにマイル加算が可能です（予約クラスG/L/V/Wを除く）。

２ヶ月間ということで、ノースウエストのワールドバリュー・スーパー14は１ヶ月間なので使えず、ワールドバリュー7は２ヶ月ですが、変更料１万円が掛かります。

帰りの日付を確定するのならいいのですが、もっといたい（ETASでは３ヶ月可能）場合などや緊急帰国の場合時の変更などを考えるなら、マレーシア航空のSUPER FLEX（６０日間有効　予約クラスＢ・復路日付変更料7000円）がいいと思います。もっといる可能性があるのなら、９０日間有効のULTRA FLEX（予約クラスＭ） もあります。短期間の方がチケットは安い場合がほとんどで、変更不可などの制限が多くあります。
旅行会社扱いの同内容のチケットの場合、変更手数料が掛からないものもあるかもしれません。

ワールドパークス®提携航空会社　http://www.nwa.com/asia/jp/worldperks/earn/air_partner.html#malaysia

マレーシア航空Web ジマット　オセアニア方面　http://www.mas-japan.co.jp/jimat/web_ocea.html

フリーバード　http://www.free-bird.co.jp/

あとは最初と最後の都市だけ決めてのチケットはオープンジョーか単純往復でぐるりと一周してくるなどはチケット購入前に考えておいたほうがいいでしょう。

コース１例として
パースインなら、パース滞在で南部と北上してダーウィンまで行って、南下してアリススプリングス・ウルル、アデレード、東に向かってグレートオーシャンロード、メルボルン、タスマニア、飛んでケアンズ、南下してブリスベン、ゴールドコースト、シドニーが最後でシドニーアウトってな感じでしょうか？

またパースからインディアンパシフィック号でアデレードまで列車の旅、アデレードからアリススプリングス、ダーウィンまでザ・ガン、アデレードからメルボルンへジ・オーバーランドなど長距離列車の利用も面白いですし、パースからアウトバック、ウルル・アリススプリングスまでのツアーなど片道ツアーもオーストラリアは多々ありますよ。

成田発着でしたが、　成田NRT－クアラルンプールKUL－パースPER//シドニーSYD－クアラルンプールKUL－成田NRT　という経路とNRT-KUL-SYD-KUL-NRTのシドニー往復を経験しています。

ＡＡＴkings　http://www.aatkings.com/au/index.php　各都市発ツアー（高め）
クレイハウンド　http://www.greyhound.com.au/　長距離バス

調べれば沢山のツアー会社の情報は検索できます
宿泊はバックパッカーやＹＨＡでしょうか？現地にも様々なツアーを紹介してくれます。
ＹＨＡの会員にはなっていかれたほうがいいでしょう。インディアンパシフィックやガンなど鉄道やグレイハウンドのバスなど会員割引がありますからいいですよ。

予めガチガチに予定を決めていくよりも、フライトだけ決めてあとはおおまかな感じを考えておけばいいと思います。現地にいけば、ワーホリ組や長期旅行者など友達になったりして、ある都市までは一緒にってこともあると思いますよ。

まだまだ燃油サーチャージが高いですね。場合によってはマイルを気にしなければカンタスの方がいいかもしれません。