Root zone rollover
I'm the author of RFC5011. Assuming you still want to do a rollover using RFC5011 semantics, I have a few suggestions:
1) Do a add of a second trust anchor as a first step. (Key B) (section 6.1 of RFC5011). Allow this to propagate through the system and ask as many validation sites as possible to report their current set of trust anchors.
2) Do a rollover/replacement of that second trust anchor. Leave the initial/first anchor (Key A) intact, revoke the second key (Key B), and add a new Key C to the trust anchor set. In other words, do Section 6.3 of RFC5011, setting the revoke bit on key B rather than key A. Allow this to propagate through the system and ask validation sites to report their current set of trust anchors. That should yield a trust anchor set consisting of Key A and Key C.
3) Assuming 1 & 2 yield reasonable results, do a rollover of the initial/first trust anchor key - again using Section 6.3 of RFC5011 and adding Key D. This should result in a trust anchor set of Key C and Key D.
By doing things in this order, you can add and delete keys in a manner that should have no impact on sites that don't support RFC5011 semantics, since the initial key remains intact in the root DNSKEY RRSet and the root trust anchor set.
In advance of (2) and (3) you should publish Key C and Key D as new trust anchors for the root zone as widely as possible using mechanisms other than 5011.