I have worked with non-native teachers in the past and the good ones are just as effective as native teachers.
I think you'll find that it all boils down to supply and demand. If you're flexible in where you want to work, you'll probably have more options, but even if you focus on the higher profile destinations there always seems to be more demand than supply for good teachers.
The issue you may face is that schools may be more reluctant to hire you from abroad as you won't fit into their "standard" mold. Showing up in person and demonstrating your professional appearance and abilities may likely prove more successful.