>Are bitcoin users allowed to use arbitrary clients?

Yes. The protocol is pretty open-ended, but the whole system is designed to be verifiable - if you don't produce something that fits the rules of the existing clients, they simply won't accept your results, and you won't get anywhere. How you produce that information doesn't matter, the proof-of-work ensures you're playing by the current rules.

As far as making more radical changes to the system, the whole thing is purely mob-ruled. If you can convince others to change over, then you change the whole system. The idea is that security and value-safety issues would be important enough to migrate everyone over, and people would do it - if they didn't, their money wouldn't be accepted any more, and they'd pretty much just lose everything.

You can run whatever software you want, but if enough other peers think your protocol sounds funny or your transactions are improperly formatted then you'll be marginalized. I don't know if this has ever been tested, though.

It has been AFAIK on the test block chain. The test block chain has been intentionally forked many times to test this sort of behavior (orphan blocks).