I don't think you need to be too concerned about the fact you don't have a degree. The most important qualification when you're looking for work teaching EFL is a certificate in TEFL.
So the best thing you can do is to get the certificate. Choose your cert course carefully, many will take someone without a degree if it can be proved that you have an equivalent level. Make sure your cert course is externally validated by a body such as Trinity, SIT or UCLES. You can also check my reply to Arun and Tim Dyke and the FAQ's at the following link:
Schools are sometimes willing to take teachers without a degree. You have many years work experience and this can be just as valuable in the eyes of some employers. Many schools see a mature teacher as an asset. In depends very much on the sort of profile they are looking for. You can check whether this is correct by looking at advertisements in the areas you mentionned, which you have probably done already. The salary offered may be lower if you don't have a degree, but then most people don't go into teaching for the money!