But what are you supposed to do if the realm wants to change government style and has majority support for it?
Well, here's a suggestion: Let the realm descend into anarchy by failing to elect a ruler. That should be proof right there that no one in the realm wants the current government to continue. Then when anarchy sets in, have someone claim rulership and reform the government.
Rebellion is currently the only way...
This is incorrect.