EIP 999 proposed to update parity's walletLibrary contract. Doesn't altering the bytecode also mean altering the blockhash, in which case, due to merkel chaining, don't all subsequent block-hashes need to be altered as well for the chain to be valid, or am I missing something?
Normally, yes, changing what code is present at an address would require changing history in some way (and thus changing block hashes).
But the implementation of EIP 999 will/would be to do this in the node software, not in the blockchain data itself. To grossly over-simplify, geth and Parity (and any other client compatible with the hard fork) would have code like:
def getCode(address): if address == 0x123abc: # affected library return fixedLibraryCode else: # look up the code in the blockchain
So the blockchain data still shows that the code is 0x0 (self-destructed), but clients ignore that and instead return the fixed contract code.
Here's real-world code in a Parity branch that implements the fork: https://github.com/paritytech/parity/pull/8406/commits/8f5b89df27704d74e397f88bf053d74d306f38ed#diff-0b65bc4c84e99a0949fb761a499d0f32R223.
Blockhash changes if there is a change in the transactions in the block. Or if we are trying to change the contents of a block.
But by EIP-999 it is being proposed to assign code to an address. And if implemented it will allow that address to have a code at its location which will take effect from a block in future. So that will not require changes in any block, hence no change in blockhash, hence not altering validity of the chain.