I would immediately implement a special role for the head of HR: official decider of all firing decisions. No one will blame the head of HR because they'll know that they were only carrying out someone else's decision, while no one would blame the original decider because no one knows who it was.