Don't count on being able to use cards of any sort. Carry cash (it's safe, don't worry). You get a better exchange rate on traveler's checks, make sure you exchange them after you get to Japan and do so at the airport to get the best rate. You can also use debit cards at Citibank terminals and do credit card withdraws at ATM machines in some convenience stores, but it's not entirely reliable, so better safe than sorry.
If you want to go cheap I urge you to look into youth hostels, as they're quite economical and the Japanese ones are quite nice. It does depend on how much you're willing to sacrifice in terms of luxuries, though, as some (not all) have communal sleeping, bathing, or TV areas. The
Yoyogi Youth Hostel in Tokyo is one I used to stay at; it has one-person rooms for 3000 yen/night and is a pretty nice facility.
For tickets I usually use Travelocity's "Flexible Dates" feature to look for bargains. There may be better methods but it's been pretty good to me in the past. (Lately it's been kind of crummy, but that might just be the economy. Sigh...) If you definitely want a proper hotel you should look into their flight + hotel packages as they can be quite economical as well. So maybe take a few passes through that and you can get an idea of what you want.
You'll also most likely want to schedule your trip for after the movie's release. IIRC they're aiming for a Golden Week release, and everything travel-related is going to be more expensive (and less likely to secure). I'm not sure how long Japanese movies stay in theaters, though; Jacky would be able to advise better on that.