All that being well and good, don't let the jobs that don't need degrees lull you into a false sense of security. If someone with a degree, esp. if they have TEFL (teaching english as a foreign language) exerience/certification is willing to do the same probably low-end ESL teaching job as someone without a degree, guess who the school will pick?
I heard that back in the bubble years, as long as you had a pulse you could get a ESL job. Now, in a recession, companies have to be more careful with their cash and want more for their yen. I don't want to make finding an ESL job in Japan seem like a huge task, but put the best foot forward, as always. NOVA does turn down applicants and the JET Program has far more people applying each year than it needs. The diehard people with degrees who want to teach in Japan might go for a second tier position just to get here. You might find yourself opposite one at a job interview. It is an employers market.
That said, I've spoken with a number of people who work in and around the Ministry of Education, and with the Ministry re-vamping English on college entrance exams and a move to make English more of a conversation/skill based subject in coming years, demand for ESL teachers could jump (I'm guessing around 2006-7). The JET Program is packing on more teachers, despite the recession and probably because they are a MEXT pet-project, but I think there is a brighter future for ESL folks in Japan in the coming years. How well salary will follow demand is a different issue.