Just back from Hawaii.
I can confirm that the ATMs i used (even though they said a fee was being charged) charged me $0 for withdrawing when using the Citibank Plus debit visa card.
Downside is that the rate was AUD1 to USD0.85.
In comparison using eftpos it was AUD1 to USD87
I changed my cash at Western Union at Wynyard station. Wasn't the best, but it wasn't the worse (AUD1 to USD84) that was mid Oct. They were happy to accommodate my request of small bills.
Depending on how much time you have until you fly, Citibank Plus Debit is an option (will take up to 3 weeks to get the card, i got it in 1.5 weeks). Just don't let them sign up you to the dud signature credit card.