I worked for a school in Vietnam this summer who advised me to get either a Subject Access Request from the police or clearance from Disclosure Scotland. I opted for the latter as I could do it online and I didn't need to send my passport off! I chose the basic disclosure (even though I knew I would be working with children!) which cost £23.http://www.disclosurescotland.co.uk/
As it turned out, I didn't need police clearance as I was only working there for the summer.Note that had I have stayed on for the academic year, I would not have been issued a visa without it. In addition to the police check, to get a work visa, you will also need to bring your original degree certificate (duplicates/re-issues are NOT accepted!).
Hope that helps.