Interesting question, and I've read some rather conflicting things about the degree thing. I know a four year is prefered...but the friend who told me about teaching oversea's went to China with only an A.A(and enjoyed his stay too).
Think the organization he used was called Sinolink.com; they pretty much took care of everything, though the pay was crap(to be expected). Anyway, look them up and see if they also know of some equally leniant groups. Good Luck!