Not that hard at all. Of course the more qualified you are at ESL (English as a Second Language) /or I guess FSL instruction the easier time you will have of it. However, lots of places take people with only a 4 year college degree.
I don't know how lucky you will get teaching French. I don't see a lot of ads around for French classes, so either the demand is not there or it is a very tough niche market to get into with a low turn-over of instructors. English, on the other hand, is in high demand still, though instructors have to work a bit harder than they did in the past. As a transient bunch, English teaching jobs open up all the time.
Might I suggest you look into the JET program through the Japanese Embassy in Canada (or consulate). It is a respected program, has higher pay than most language schools and the hours are often better. JET has its flaws, but fewer it seems than the likes of NOVA, AEON and the like. Good luck.
NOVA etc, I hear about 250,000 yen a month before taxes, on the barrel head.
JET, around 300,000 yen a month before taxes, often with subsidized or free housing, low-cost health insurance, moderate life insurance, and all the benefits that come from being paid by taxpayers yen!
(expect about 40,000 in taxes)
Private tutor. Depends on how good a teacher / self promoter you are and the market you are in. I pay my Japanese tutor 1000 yen a lesson / hour, one on one. Apples and oranges I know, but at NOVA now they have a trial lesson deal where you get a skill level check, "counseling," eight lessons, and texts for 20,000 yen (about 3000 a lesson). That is a good deal. If you can match NOVA in services available, you can charge that much too.
If you are a private tutor (and I don't know how much they bring in) of course either you will need to go to your students' home/office, or you will need some place they can get to. Start figuring in all the extra costs, and it makes a lot of sense to go with NOVA or JET to make sure you like this gig before sinking serious time and money into making a business out of the private eikawa game.
The more certificates for teaching ESL/FSL after your name, the more cash you can go for.
Usually the normal price for tutoring English is around 4,000 yen/hour, it might sound like alot of money but it also takes alot of energy too. It's a great way to make ends meet, but if you want a career out of it you need lots of connections (got those 窶堙溪?堋｢窶堋ｵ handy?).ﾂ I suggest you have ESL and experience at teaching and of course plenty of patience before trying to tutor students... And by the way some of the big companies don't let you tutor students in your free time, so read your contract before you sign up. Also, major cities have more customers but more competition, remember that.
What some people do is they teach at a school for awhile and build up students and connections and then they go on their own as a tutor. You won't get rich, but it'll be a much more flexible schedule then if you worked at say NOVA or GEOS. You'll also make some good friends