Many states have backdoors that are regularly used to hire exceptional non-traditional candidates such as practicing Lawyers, experienced Engineers, and science/engineering PhDs (even PhDs in the humanities if the PhD is from a prestigious name).

But you need to get your resume in front of the right people -- namely, folks in the central office (or maybe principals) who view your area as a strategic/difficult hiring area. Easy peasy in CS these days...

Also check out private schools.