Most of the english teaching jobs in Korea are at after-school academies (which are, as you say, tutoring type places). For that you basically just need a bachelors degree in anything, and to be from an English-speaking country.
Public school jobs are available, though, but they are a bit harder to get and I think they prefer people with some background in education*, but the stated requirement is still basically the same: citizenship of Australia, Canada, USA, Ireland, New Zealand, South Africa, or UK; bachelors degree in any subject from one of those countries; completely clean criminal record; clean health check.
Check out Waygook.org
and Dave's ESL Cafe
for a start, and for many people considerably better informed than me.
*Having said that, I think some places prefer people with no education qualifications, because it allows them to keep you at a lower pay grade for longer under the foreign teacher employment contracts here.