I would recommend the same "Leave", but make things clear with he could be a good start, just because is your boss is not the only-rule-decision-maker, express your anger if he get hot-head, punch that f%ckr. :)
Even if you go over his head, you've probably still got to work with the bastard - with the added problem that he'll be looking for every little fuckup you make to construct a case against you. Generally, I find it easier to find a new job and then leave politely rather than work around difficult superiors.