I am German, therefore non-native, although I have a TEFL certitificate which I did in June/July last year in Barcelona.
I live in Barcelona since October 2005 and have found a job almost immediately without being a native speaker. Neither have I university degree. I could provide 15 years of imports/exports experience though.
I never applied with the big schools such as International House, Berlitz, Inlingua etc as I am pretty sure they will not employ me. Although everybody says I speak like a native it is just against their company's policy. But I am happy working for small schools anyway.
Sorry, no experience with Greece employment but would be eager to learn about it myself.
Good luck for you! Frauke