Hi and Welcome!
I'm also heading out to Melbourne in October, I land on the 9th flying from Gatwick.
I will do my best to answer your questions, but as I have not been, I am going on what I have found/heard.
- What is the best and cheapest way to travel round oz for backpackers? - trains, coach, flight? Coach is the cheapest form of travel, internal flights can be cheap as well and are a LOT shorter than coach journeys.
- What is the best phone network when we get there in terms of getting sim cards? I have heard good things about Telestra.
- Which bank is best and has most ATM machinnes? Commonwealth Bank seems the most popular and has the most ATMs, https://www.commbank.com.au/personal/international/backpacking-in-australia.html
Hopefully somebody who has actually been can clarify better. HTH.