In the US at least, you can -- and should -- set up a bank account with a debit card. Sometimes it requires a parent to cosign, but it is quite worth it.
I wonder, can't you buy a anonymous credit card from a department store?
That's not terribly common in the US. It's possible to buy VISA or AMEX gift cards in some stores, but the markup tends to be significant (10%+).