During college I lived in central Tokyo on a budget that was much less than what I had in the States (120,000 jpy) - working near full time mind you.
Started out by living in a few different netcafes for a month and moved into a humble flat with initial costs under 100,000 jpy.
Now with a non-Japanese wife and no guarantor, we pick places where these fees are non-existent and landlords or organizations are okay with foreigners working non-traditional jobs using guarantor companies (monthly guarantor fee of around 2600 jpy). More so than the deposits, it sucks I get discriminated against for my race.