True, and I know what's wrong with my solution (after some discussion on #bitcoin-dev): The final signature by itself is malleable, because for every ECDSA signature (r,s), the signature (r, -s (mod N)) is also a valid signature (of the same message.)

And since you can put a "random" number as a signature, it would be impossible to prove that you'll get the "smallest number" (who knows what kind of mathematical tricks you can pull.)

It's that final signature causing grief and I think it would be very difficult to fix that.