"Should I contact universities by phone, email, snail mail? What do they prefer over there?
Are there many non-English degree professors teaching English in the universities?"
1. I always think a snail mail package is much more impressive, but more expensive and time-consuming on your end. You'll have a hard time getting through to the person who actually hires on the phone. And email is an easy way to contact a huge numbers of unis.
Your best bet is to look at job ads (www.eslcafe.com) and follow the directions PRECISELY. Many people don't and the applications just get thrown out.
2. Yes, most people don't have English degrees. A master's degree in anything is good enough, especially for the lower-level unis out in the countryside. It might be a challenge to get a job in Seoul with something not related to English, education or TESL.