Ok so thanks to Chris Backe at http://chrisinsouthkorea.blogspot.com/ for supplying me with the Korean for my how to be a vegetarian phrases. They are written in Hanguel as follows:

1. I’m a vegetarian – 나는재식주이자 임니다 – Na Nun Jae-shik-Ju-ee-Ja- im-nee-dah

2. I don’t eat meat of seafood – 해물하고, 고기안먹어요 hae-mool hago, gog-ee an-mogoyo
3. Does the […….] Have meat in it? – […………] 고기있어요 goggee iss-o-yo?
4. No meat – 고기없어요 goggee op-soh-yo

Secondly as was pointed out by someone else on the comments blog there is a chain of vegan restaurants in Korea called the loving hut. http://www.lovinghut.kr/kr/. I’ve been to the one in Ulsan and it’s pretty good and very cheap, if you don’t mind a long wait and slightly cold food. They do a mix of western and Korean food, and show a delightfully indoctrinating TV channel mysteriously called ‘Supreme Leader’.