How could the protocol or client be altered to mitigate a timejacking attack?
Solution number 1 would mitigate this problem, but the attacker could try creating enough nodes to flood the network anyway (see cancer nodes). It would not be likely that the attack would be performed, but it would still be possible.

Solution number 2 would help with this problem, although it would cause a lot more problems with everything else. Imagine the excess traffic caused by tens of thousands of Bitcoin clients dropping all of their connections each minute and reestablishing them with new peers. You would need to exchange a lot of information this way you wouldn't normally have to (version, verack and inv messages during each such reconnection at the very least). As the attack does not appear a likely threat for the Bitcoin network, such overhead would be unjustifiable.