Last I heard only citizens of Canada, US, UK, AUS, NZ and South Africa with a BA degree can apply for a Korean teaching visa (E-2). Please also contact the closest Korean consulate and ask them.
Another option can be China, they seem to require (only) that you speak English well and have an university degree to get the teaching visa. I suggest you post your resume to many sites on the internet.

Good Luck!