What is the best way to "fire" my advisor? I have had it with my advisor's unethical behavior, demanding people to be removed from papers, removing my cosupervisor without telling me and insinuating that he has "appointed a new one".

What is the best way to break up with him? The PhD school already has a procedure in place, but do you advise I speak with him before I start this process?
Do I tell him the very truth for why I don't want him anymore or simply state some other reasons and stroke his ego anyway?

UPDATE: He wouldn't meet with me, so I didn't even have a chance to be hesitant about speaking with him. He suggested a third supervisor other than the one I had chosen, and I respectfully declined.
If you are having trouble with your advisor, I think you should talk to your department's director of graduate studies (or the equivalent). At most universities (at least all the ones I have been at), there is someone whose job it is to handle paperwork and the such. They are also there to act as a kind of ombudsman, helping students handle disagreements with advisors.

I've had this role before, and I view myself as squarely on the side of the student. I can fight advisors on their behalf. I've done all of the things you are asking for: navigating committee changes, telling an advisor they are no longer a students' advisor, etc.

I think it is important to document such behavior on the part of the advisor. Even if your breakup with the advisor goes poorly, an official record of such behavior might make the department think twice about allowing such a pattern to continue.