He elects a majority of the board members through his shares. In fact, the board can indeed fire him even if he (as a member of the board) votes against the rest of the board. I wouldn't characterize the current board as being Mark loyalists https://investor.fb.com/leadership-and-governance/?section=b....

Even as a controlling shareholder, the ex-CEO could take months to go through the process of nominating new board members and holding a shareholder election according to the corporate bylaws before his new hand-picked board members could hire him back.