What kind of job?
Foreigners in Japan must usually speak fluently Japanese to find a regular job in a company, unless they are expats - i.e. sent by their company to a Japanese branch office. For this reason, a disproportionate number of Westerners living in Japan start by teaching their mother-tongue, or any other language they master. English is by far the most taught and most demanded.
It is sometimes possible to get a good job without speaking Japanese, in particular if you have a lot of experience and outstanding qualifications - or if you are lucky. As a rule, the better your Japanese (and English, if you aren't a native speaker), the easier to find a job. The most demanded sectors for foreigners, teaching notwithstanding, are: IT, accounting, finance, translation and entertainment (bars, nightclubs, hostessing, dancing...).
Tokyo has the largest range of jobs and the highest salaries, although Osaka and Nagoya are also competitive (and cost less in accommodation).
To learn more about teaching English in Japan, read the following article about the experience of an American teaching at Nova :
The Unbiased Truth About Nova (by Brooker)
Jobs Search Engines
Search engines are a convenient way to find the right job at the right place.
Teaching Jobs
Private one-to-one lessons
The sites listed below all offer free online registration for teachers who wish to teach one-to-one or small group language classes. All of them are for English teachers. Some include other languages as well (specify in brackets).
Teaching Ressources and Job Listings