Well, for starters I must say that the problem with ECDSA nonce can be avoided even when using ECDSA via the same method used in Ed25519, and indeed this method is not even novel to Ed25519. But, let's assume we need to change the signature algorithm for some reason.
OP_CHECKSIG does not support different key types per se. The public key given as input is either an uncompressed or compressed EC point, starting with 0x04, 0x03 or 0x02. Any other starting byte could be used for different transaction types, if desired. However, a separate opcode would (IMHO) be cleaner.
The only required changes are on the script side, either modifications to OP_CHECKSIG opcode or the introduction of a new opcode. And after this, miners need to start accepting transactions containing the new style signatures as "standard" scripts.
All "full" bitcoin clients verify all transactions that are present in a block (run all scripts). This means that they will refuse to accept a block that can not be verified (even if it only has one transaction failing verification). This means that if such a change is incorporated, the block chain will fork for the clients that do not support such transactions.
Nearly all clients will need to support the new signatures and the clients that do not will become unusable when encountering the first block that has a transaction with a new signature.