We may not need to change any thing about block header.

Just imagine I have found a new block with a valid negative-hash attached to it (not included yet), so I could broadcast it to other nodes as always we did before. for the next block, while we have the previous block's hash in the new block header, miners could also find a proper place in COINBASE transaction for the previous negative-hash value (if exists) and chain it to the new block header by its regular merkle-root. This is how such special negative-block could simply get fit in Bitcoin blockchain with less changes in major aspects of the current working Protocol.

P.S.: Just as a primary incentive, this also could help we access our coinbase rewards / fees with less confirmation.