I have multiple times deboarded a plane before take off. Due to change in business plans, flight delays, etc. In one case a passenger was sick on board and I asked to deboard as I didn't want to risk getting their cold.
This was all on Asian airlines. My few experiences on United have been terrible.
So in this case I'd say the regulations guiding airlines is fair. United's execution of these regulations is the problem. There are a million things United could have done in the chain of events to have avoided facing a PR backlash. As this is HN, I'd give a simple technical solution that would have avoided this whole problem:
The computer could have deboarded 8 passangers at random from order of lowest priority. United could have explained that if their employees don't catch this flight another flight with XXX passengers will be delayed / cancelled. This would allow the supervisor to use their own discretion to allow 4 of the 8 passengers to reboard.
Making the practice of "overselling" illegal is not the solution. There are times where problem could be cause by equipment swaps changing seat numbers. If we stop the airlines from overselling then travelling will become a lot more expensive.