For the purpose of this cut, Episode I, just inserting an introduction of Maul as Grievous and maintaining the name change will do for a set up.
The "Rule" of 2 is obviously not a rule as Vader and the Emperor plot to get Luke in the OT-- as you point out, so any reference to a "rule of 2" is about as meaningful as a reference to midiclorians. It's outdated by the time of the OT and kind of confusing-- so why not cut it?
The chronology of GG/Maul, however, doesn't really have to violate this. Maul/GG is "killed" by Obi Wan in Episode I. He doesn't have a role in Episode II, but that's fine because the story would be that Episode II is when Palpatine is developing the techniques that save Maul/GG and turn him into the Grievous robot of Episode III. This happens, one presumes, in the same laboratory where Vader is rebuilt. It happens off screen since it has no bearing on the events of Episode II.
The reveal of Grievous' identity to Obi Wan during their Episode III duel is a wonderful opportunity-- but this is the one sticky point about Commander Courage's plan: if Grievous robot and Darth Grievous of Episode I have the same name-- doesn't everyone know it? Maybe the Jedi won't, but the audience will and that's just as important. To work best, the moment Obi Wan learns Grievous is the same Sith who killed Qui Gon should be the moment the audience realizes the same thing.
How can this reveal be preserved for the audience?