Here's a good place to start if you want to work and study abroad. It's a web-page hosted by my alma mater, University of Michigan.
http://www.umich.edu/~icenter/overseas/work/waoverweb.html
Some decent information there.
The first time I went to Japan actually was under a paid internship program. They're hard to get and basically you need to be an overachiever to be accepted. There are some other ways to go about studying abroad, but most of them require an expensive layout in money. It
can be done, but you'll be looking at several thousands (or tens of thousands) of dollars if you cannot secure financial aid.
One route you may take is to contact an American college and see if they offer a study abroad program. Infact, I think this is probably the safest bet. It has the advantage of letting you finance some of your study with U.S. student loans (payable to the U.S. institution) which then generally provides a grant to the foreign institution.
Chances are whatever universities are near you have some sort of study abroad program. Finding one that is in Japan (or in the specific area of Japan you wish to go to) may be tricky, but not impossible. Also if you manage to sign up via a State institution, the enrollment cost will generally be far less than if you did a direct enrollment in the foreign university. Plus as a nice side benifit, these programs usually provide excellent support structure for their students and already have agreements in place with the foreign instututions on how to handle matriculation of earned educational credits.
Call around and if possible set up a meeting, or a walk-in at your local college and find out.
Mal