I live in the 2nd hottest neighborhood in the city. You can rent an apartment within 4 blocks of me, tomorrow, for $800 a month, and you'd have many choices. If you were willing to live further out or in a less prestigious neighborhood you could trade up on size, too.
[+] Tokyo is very much not monolithically tall buildings. I live in a 45 story highrise; less than 25 meters away there exists single-family housing and 3 story apartments. The average density is pretty high, though -- here in Meguro it is about 2.5x SF's citywide (50k people per square mile vs 20k).