PhD in Management Science and a faculty position in CS
At least three faculty in my department (including our current head) have PhDs in electrical engineering, at least one has a PhD in mathematics, and at least one has a PhD in operations research.  If a faculty candidate is actively publishing good research in computer science conferences and journals, which department gave them their PhD really doesn't matter.  (And if they're not actively publishing good research in computer science conferences and journals computer science research, they won't get hired, period.)

Most junior faculty candidates don't have significant teaching experience anyway, so that aspect really doesn't matter much either.  Sometimes it can be a bit tricky to find courses for new faculty with non-standard backgrounds to teach, but if they're really doing CS research, something always fits.