Did you actually read the page you linked to? Here is what it says about opening an account with only a passport: “If you open an account within 6 weeks to 3 months (depending on the institution) of arriving to live in Australia, you will need only your passport.”
I travel all over the world and never use anything other than a debit card. You say the exchange rates are crappy and they charge you - but have you sat down and worked out all the options? Would the amount charged, while excessive and annoying, actually work out to something relatively negligible - say, you write off $40 against the vacation exchange rates, then relax about it and enjoy yourself.
Alternatively:

I refuse to use traveler’s cheques.
Out of interest, why? If it weren’t for this stipulation, then they would fulfil all of your other criteria.

Did you actually read the page you linked to? Here is what it says about opening an account with only a passport: “If you open an account within 6 weeks to 3 months (depending on the institution) of arriving to live in Australia, you will need only your passport.”
The OP’s not arriving “to live in” Australia, though.

I travel all over the world and never use anything other than a debit card. You say the exchange rates are crappy and they charge you - but have you sat down and worked out all the options?
There are actually online tools that will do this for you—that is, they screen-scrape the major banks’ exchange rates and debit card fees for foreign ATM withdrawals, and then recommend to you whether it’s better to use your debit card or to change your money in advance. If it’s better to change money in advance, they’ll tell you which bank or bureau de change offers the best rate (including commissions and fees). In many cases, the savings can be substantial. One tool I can heartily recommend (though it’s UK-specific) is moneysavingexpert.com’s Currency Power Picker.

I did exactly this when I took an extended holiday in Australia in 1999–2000. I had no problems opening an account and getting a debit card; all I needed was some ID. Then again, the rules may have changed since then. Why not simply contact an Australian bank and ask? Wikipedia has a list of the top Australian banks, whence you can find their web pages and contact info.
I did try that, and got a very polite, “Why not come into one of many branches and talk with the manager…”

I travel all over the world and never use anything other than a debit card. You say the exchange rates are crappy and they charge you - but have you sat down and worked out all the options? Would the amount charged, while excessive and annoying, actually work out to something relatively negligible - say, you write off $40 against the vacation exchange rates, then relax about it and enjoy yourself.
Alternatively:Out of interest, why? If it weren’t for this stipulation, then they would fulfil all of your other criteria.
I learned a few years ago that they’re just a massive scam. I paid a fee to get them, and then wasted most of my vacation trying to find a place to cash them. When I did find a place they were more than happy to screw me over, knowing I had this silly piece of paper that no on else wanted. Never again.

The OP’s not arriving “to live in” Australia, though.
Well, depends on what he, and the web page I linked to above, means by “live in”. The OP says he’s going on an “extended vacation”. What the web page says certainly does (or did, at least a few years ago) apply to working holidays, whereby nationals of certain countries can take a vacation of up to one year in Australia, and are free to take up employment during their stay, subject to certain restrictions.

I learned a few years ago that they’re just a massive scam. I paid a fee to get them, and then wasted most of my vacation trying to find a place to cash them. When I did find a place they were more than happy to screw me over, knowing I had this silly piece of paper that no on else wanted. Never again.
I’ve never encountered a problem anywhere in the world with traveller’s cheques. There are a couple of things you need to keep in mind with them though:
– Some banks offer their account-holders no-fee traveller’s cheques. Sometimes organizations, such as AAA (in the US) and CAA (in Canada) will do the same thing for their members. Worth looking into before you go.
– If at all possible, buy traveller’s cheques in the currency of the place you are going to. You can buy traveller’s cheques in Australian dollars; I certainly have. Such cheques are cashable at far more places in Australia than cheques denominated in US dollars. (I’ve seen American travellers get quite upset when their US dollar-denominated traveller’s cheques are refused by merchants, while my locally-denominated traveller’s cheques were accepted with a smile by the same merchants.) Besides, when the cheques are locally-denominated, you shouldn’t be dinged for fees/exchanges when you cash them–IME, especially if you cash them at a bank, you get exactly what the cheque says it is worth, not a penny less.
The last time I went to Australia though, I just ran my Visa card through ATMs. (My Canadian debit card will work in foreign locations, including Australia, but I will pay dearly for the privilege.) That would be the easiest thing to do, I think. You may pay something for the privilege, but you can work to lessen that while still at home by taking the cash you were going to take with you for your bank account and creating a credit on your Visa (or whatever card is your preference) account. By drawing against that credit, you’re not going to be hit with interest for what is essentially a loan from Visa. Without the interest, the fees and exchange costs are pretty reasonable.

…then wasted most of my vacation trying to find a place to cash them…
In my experience, they can be cashed at most hotels, and at all banks. And spent in many stores too, that will give you change.
Your OP says you want to do the exchange before you go, but not in cash, and you eschew travellers’ checks. IMO you’re asking the impossible.
Did you consider my “write off exchange charges as a vacation expense” proposal? Sounds like it could be better for your blood pressure.

Are there American banks like HSBC and Bank of America that have branches in Aussie?
The last two times i’ve gone home to Australia for a visit, i’ve just used my Bank of America debit card to withdraw cash from Westpac ATMs in Australia.
Because Westpac and BofA are part of the ATM Global Alliance, there is no fee for using the ATM, and the transaction fee for a cash withdrawal is 1%. While i’d obviously prefer to pay no fees at all, i think 1% is pretty good for the convenience of being able to withdraw cash using my BofA card, with no hassles like traveler’s checks or getting a new bank account. Even if you withdraw 2 grand in cash during your vacation, it’s cost you just $20 for the convenience. Small change when you consider the cost of a flight to Australia and all the other costs of the vacation.
Westpac is a big bank in Australia; there are Westpac ATMs everywhere, and i never had any trouble finding one in Sydney, Melbourne, Coffs Harbor, Goulburn, and in Wellington, NZ.
I would get a prepaid Visa from the post office, you can get them in small amounts so if you lose one it is not the end of the world. Makes life a lot easier but of course you can’t draw down cash.

Did you actually read the page you linked to? Here is what it says about opening an account with only a passport: “If you open an account within 6 weeks to 3 months (depending on the institution) of arriving to live in Australia, you will need only your passport.”
I read it, but missed that bit. My apologies.