Another (see my posts on Love Hotels, Capsule Hotels, Hostels and Couch Surfing) low budget accommodation solution is what I call "wank-booths".
All around major cities you will see posters for what look like comfortable faux-leather chairs in front of a computer in a wooden box. That's exactly what they are, and you can rent them (or do away with the chair and just have a padded floor) for as long as you like. Prices range from 300yen for an hour to something like 1,500yen for 12 hours.
They're usually 24 hours, and weird as it may sound you can sleep in these places without any stigma. Several of my friends have done so for convenience. It's a lot easier than finding and checking into a hotel or hostel, and the price is much better.
Although technically an internet cafe, it's not uncommon to find them also called manga cafes and come with a large library of tankoban. Some places, however, may make you rent porn to qualify to stay. Avoid these ones.
The floor/chair is usually perfectly good enough for a fair night sleep, though if you have a problem with cigarette smoke you may be slightly uncomfortable. Also, if little groans from the cubicle next door affect you in a bad way maybe you should look for a hostel or capsule hotel. Having said that, last time I stayed in a business capsule there were more than a few groans in the night.
Other posts in this series: