Here are some pictures of Tokyo in 2012. In late March, I got a new job and moved from Akita to Nishitokyo, a city in western Tokyo.
Before I moved to Tokyo, I came for a few visits (job interviews, training, apartment hunting, etc.). The cheapest nightly lodging in Tokyo, other than the park bench, is a net cafe. You generally need to speak Japanese or otherwise have some idea what to expect, but the process is not so complicated: get a private booth at an internet cafe, sleep in the reclining chair (if your booth has a chair) or on the floor of the booth (if your booth is a floor type), set your cell phone alarm, and crash for 8 hours. Net cafes tend to have showers, so you can pay a few dollars in the morning for to clean up, if you want, and doubtless there are free soft drinks and coffee. Some net cafes are louder than others, though, so if you can find a place not so close to the bars and night clubs, it'll be quieter and better for a nice night's sleep. Net cafes often have "night packs", overnight 8- or 10-hour specials that cost fifteen dollars or so.
It turns out renting apartments in Japan is quite expensive. They want the first two months' rent, a one month damage deposit, a one month fee to be paid to the realtor (you won't meet the landlord until after you sign a lease, quite possibly), and possibly a few hundred dollars to put in new locks. And when you leave, if your place has tatami floors, you'll lose a few hundred dollars of your damage deposit on replacing the mats. That's all quite daunting, financially speaking, but one good point is that the realtors are well organized. I had a list of places I found online, and they were quick to get me around to see all of them.