Tada,
To you, the concept of living here permanently is not BS. I have no problem with that. However, to have visited only on vacation a few times is not really a reason that will seem strong to an employer to live here forever. But, that is not important, really. What I intended was that you should avoid overly enthusiastic remarks like that because there are tons of young people who apply, and their main reasons for staying are sex, anime, partying, and sex. Try not to look like them.
How long should you apply? For JET, you will have to wait for the application itself to be made available. Look around October or November.
For other places, as I wrote (and answered as specifically as anyone could):
"they generally put out ads 2-4 months in advance of the start date"
It's July now. This is the beginning of a slow time of year for eikaiwa. Not impossible, but slow. How long will it take you to give notice on your apartment, pack up your belongings and store them while you are in Japan? How long is the visa application process (answer: 4-8 weeks). Timelines are one thing, but if I were you, I'd shop around and see what sorts of jobs are out there for newcomers. Do some research on locations, salaries, benefits, types and hours of teaching, etc. Don't jump into things.
It's a buyer's market right now. The market is flooded with teachers. Choose wisely, but don't expect the first employer to say yes.