By specifying such a large nonce prepended to the message, if an attack on SHA256 were found then the the attacker, by engineering certain parameters into the nonce would probably find it easier to find a collision. The recipient of the signature doesn't have any way of telling one nonce from another so can tell whether the nonce has been "tampered with".
Well, I think we're stuck then:
I don't believe your proposal actually provides a secure solution with ECDSA_SIGN(SHA256(fixed_string+message)) under the assumption that the hash function has a weakness that makes collisions computationally feasible: An attacker knows the fixed string and can often control the complete content of the signed message, so they can search to produce same value to sign as some attacker selected transaction. They compute and take as much time as they need, you sign, and they've stolen all your coin.
They can even attack all the known bitcoin keys at once with linear speedup, since for each key they can compute N target hashes to collide and then collide any one of them opportunistically. (A theoretical weakness you pointed out earlier for which you suggested including the address).
What I'm proposing would not have that particular weakness, unless you assume the attacker can create collisions even in the face of a large amount of sender selected random data. It does has the weakness that given a key-signed-message they could potentially produce a second valid signed message which used a different nonce and had the same hash, but the simpler scheme has this same weakness assuming there was any replaceable data in the message.
The assumption of hash function weakness would be the same in each case, but I don't see how the latter could directly be used to steal all your bitcoin. Nor could it e.g. be used to have chosen input to ECDSA should some attack be discovered there.
So to summarize:
Attack 1. Attacker finds some fixed_string+message and message2 which have the same hash, and where message2 is the hash of a bitcoin transaction stealing all your money.
Sender selected nonce kills this one dead. (assuming that they can't perform the hack without knowing the complete input to the hash function)
Attack 2. Attacker has some signed message and finds another message that with the same hash then claims you signed it. This doesn't let them steal all your bitcoin directly but might allow them to exploit some other service which depends on address signed messages. (though you can prove after the fact that there was an attack, by presenting the message you did sign)
Both are vulnerable to this, the 'sender' selected nonce is only more so if acceptable fake messages couldn't contain any high entropy portions: due to the need for anti-replay, account numbers, etc. in many applications this seems unlikely. Sender selected nonce has the benefit of needing to collide an arbitrary hash rather than finding a pair of messages in advance.
Attack 3. Attacker finds some fixed_string+message such that the hash exploits some weakness in ECDSA (perhaps combined with other preexisting signatures) which discloses the private key.
Sender selected nonce kills this one dead.
If you don't take the assumption that the hash function is weak (or that chosen values for bad inputs to ecdsa are common) then I think both are equally secure.