>>>>What is the difference between TEFL, TESOL and CELTA ? Which one(s) is (are)likely to be most recognised ?

CELTA (Certificate in English Language Teaching to Adults) is simply a Certificate awarded by Cambridge ESOL.

It is undoubtedly a popular qualification especially in Europe, one that will open many doors but it is not necessarily the only one.

Quality TESL/TEFL Certificates are also widely accepted.

There are many good schools around the world that will happily accept TESL/TEFL Certificates issued by reputable organizations other than Cambridge, so you can shop around.

As for which would be the best course for you it really depends on how much time, money, and commitment you are prepared to invest.

There are quite a few good courses both online and onsite to choose from. You could start by taking a look at TEFLWatch.org. This is a site where TESL/TEFL courses and course providers are independently reviewed and rated.
http://www.teflwatch.org/forum/index.php/topic,1477.0.html

>>>>>I am not a native English speaker, do you think it will be a handicap?

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 nt so easy to find.