When I'm visiting Tokyo I tend to stay in this place which is about
10,000 yen a night:
http://www.tokyuhotelsjapan.com/en/TI/TI_KICHI/index.html
Not the cheapest you'll find, but this place has the advantage of being
in Kichijoji, which is a nice place in itself, about 10 mins from
Shinjuku on the Chuo line, and 25 mins on the Inokashira-line to
Shibuya. Hotel itself is budget Japan business traveler-style.
Full disclaimer: I'm a Kichijoji addict. Iseya, Harmonica Yokocho,
Yodobashi Camera, Inokashira Koen, Jindaiji, Ghibli Museum. Can't get
enough of it.
-Mike