Just because a contract is mutable doesn't mean that everything needs to be.
For starters, not all functions on the contract are supposed to be mutating. Marking those that are as such would catch accidental mistakes when unnecessary mutations happen.
Then there's the issue with structs, collections etc all also being mutable by default, which is separate of contracts.
Finally, none of this actually requires any mutability at all. A contract could treated as a pure function that takes initial state as input, and returns the new state as output. Such a function can be written without any mutations at all, by constructing the new state piece by piece from the old one.
Sure, it would be a more verbose (although functional languages usually offer shortcuts like "give me a copy of this object, but with these fields set to different values", making it not so verbose after all). But on the other hand, it means that you have to explicitly consider the effect of every operation of the contract on every bit of state. "Don't repeat yourself" is not always a good thing - when it comes to security, you often do actually want to make people do redundant things, e.g.: http://www.atlasobscura.com/articles/pointing-and-calling-ja....