As you can see, the nSequence of all the inputs are hashed together and are used right from the first message block.
Yes, because you use SIGHASH_ALL. But I used SIGHASH_NONE, which should clear some fields. And in general, you can grind the solution with SIGHASH_SINGLE, combined with SIGHASH_ANYONECANPAY, and put a higher output value than input value (to prevent it from being stolen).
And in that case, I think you should be able to pick a different nSequence. But it can be confirmed on testnets or regtest first with easier puzzles, before grinding the reward.