Finding a good apartment or any apartment in Japan can be a real pain for foreigners. Most apartments require a guarantor on the lease, basically someone to vouch for you. Unfortunately, that often proves somewhat of a difficulty for us foreigners because no one wants to vouch for us hooligans :-(. If you're lucky, your company will sign as your guarantor. If you're unlucky (like me), they will not. Below I present a few foreigner-friendly, no-guarantor-required housing options that have proved quite handy to yours truly.
Leopalace 21
Leopalace is what's known as a "weekly mansion," an often short-term quick-sale housing option popular with students, young singles, and salary men on longer-than-usual business trips. Their business model is different from a traditional lease: The contract can be very short term; most of the places are fully furnished with things like a TV, microwave, and fridge; and the prepaid rent includes everything like utilities and Internet. It's basically like living in a college dormitory, minus the wild frat parties down the street and obnoxious roommate. Around the time I was leaving my English teaching job in Tottori, I signed up for a 3-month contract with Leopalace. They're nationwide, so the local Tottori office found me a place in Tokyo. I prepaid the rent, signed the contract, and was on my way. They told me to pick up the keys at a certain Leopalace office in Tokyo.
For somewhat obvious reasons, this business model is quite compatible with foreigners. I noticed they even have an English-language website available now that promises "Staffs who will assist you in English" (damn, I love how they pluralize "staff"--so cute). This is a great sign because it means they're working to attract the foreigner niche--something few Japanese companies do.
UR - Public Housing
During my 3-month stay in a Nakano-ku Leopalace, I had found a solid job in Tokyo and was ready to move on to something a bit more spacious than the 13 square-meter box I had chosen to live in (It was cheap--gimme a break). Again I was faced with the guarantor conundrum. I asked my new coworkers for their recommendations, and one fellow ex pat replied, "public housing!" "Ewwwww," I thought. My mind filled with images of barred windows and gun-shot riddled nights living in fear. But this is Japan's public housing. And I was wrong. Big time.
I visited their Shinjuku office with some ideas of which part of Tokyo I would like to live in. They recommended a few of their UR buildings and showed floor plans of available apartments in my price / size range. The staffs did not speak English. This may depend on who you get, but don't expect English-speaking service at UR. Nevertheless, they were extremely helpful, and the foreigner-without-a-guarantor thing was a non-issue. Long story short, I signed a 1-year lease with UR. It was much closer to a "traditional lease" (utilities were separate & the place was unfurnished), with the welcome exception being the foreigner-friendliness.
UR does have an English-language website, but it doesn't contain near the info the Japanese one has. But if you live in Japan, then you're used to that already. Immerse yourself and good luck!