For one thing, you would have to get foreign licenses. It probably won't be easy. For example, I've heard that the U.K. CFI practical is brutal, more so than here. Another thing to consider is there are far fewer flight training opportunities abroad than here, primarily because fuel is so expensive. Think about it. So many foreign nationals come to the U.S. for their training because the cost is cheaper in comparison. One other point is you would need the right to work in a foreign country, and that schools there will probably give preference to their nationals.
Just the same, you might check around. I had a friend who got a job working in Saudi Arabia training pilots. He had a great deal of instructing experience before he got the job, though. Sometimes, Captain Mac at Flight Crews International, www.fcilax.com , runs notices in his bulletin for instructors at foreign schools. But, here again, these are for people with a great deal of experience.
Under NAFTA, American and Canadian instructors are free to instruct in each country, without having a greencard/social insurance card. All you need to do is find a flight school to sponsor you.
Keep in mind, however, that instructing is very different in Canada. There is no such thing as a CFI, CFII, MEI, etc. We use Classes.... a class 4 is your beginner. To get to higher classes you need certain requirements (ie. solo recommends, passes, etc). It's also very unlikely that a new class 4 would get to do some multi teaching here.