Native-speaking English teachers are short supply here. Salaries reproduce the high demand. The majority of teaching positions have need of an applicant to be a native speaker of English and have a university degree. A definite advantage for you will be the teaching certificate and some experience. Work is obtainable at bilingual colleges, language institutes, and universities.
Interviews are characteristically in English, but as a working resident you will probable want to pick up more than just tourist Spanish. The Universidad Santiago de Cali and the Pontifica Universitaria Javeriana have Spanish programs for foreigners. A private tutor is quite easy to come by. It will not be a problem for you to find someone to help when you need something done in Spanish as Colombians are very friendly, sociable and always ready to help.
You need not worry about the news reports. Call, write, or email the schools and institutes to get a feel for their needs and requirements. Check out the web sites. Assemble your diplomas, certificates, and reference letters. Do not forget to bring together materials like maps, postcards, flyers, magazines, and memorabilia from your hometown. These will be priceless for your conversations with students.