Signatures are dependent on the data they are signing and my public key, my public key is fixed but the data I am signing is not. I can add and remove transactions to the block to change the output of the signature. (Technically with ECDSA signatures you don't even need to do that, you just change the nonce used in signing to get a different signature)
There is no
ECDSA involved. Just
sha256.
Yes there is, when you sign a block with NXT you sign it using ECDSA. It is this signature that is used to calculate who gets to sign the next block and therefore you need to iterate through different ECDSA possibilities to produce the lowest value when you combine it with your public key and take the SHA256 hash of the two combined.