I think you can safely assume that looking for work outside your own country is going to be more challenging, but a lot will depend on where you go. For example, if you wanted to go to Ireland to teach English than you would be in direct competition with native English speakers.

In other words, if you were on a shortlist with a native English speaker who had very similar qualifications and background to yours then the post would be more likely to be given to the native English speaker. However, if the native English speaker was under qualified or had no experience you would stand a very good chance of getting the job despite not being a native English speaker.

The scenario would be different if you went to a country where native English speakers qualified to teach are not so easy to find.

As for certification TEFL/TESL/TESOL certificate courses, including Celta, will train you to become a teacher of English as a Second or Foreign Language. Bear in mind that in most places the basic requirements for entry level teaching positions are a degree plus a TESL/TEFL certificate - not necessarily a CELTA.

PM if you have any more questions.