Here's how I would do it:

MacroSequence
Code:
FrostNova = { [[
/stopcasting
/cast Frost Nova
]] },

NovaSequence1 = {
    reset = { seconds = 25 },
    "/click FrostNova", "", "", ""
},

NovaSequence2 = {
    reset = { seconds = 25 },
    "", "/click FrostNova", "", ""
},

NovaSequence3 = {
    reset = { seconds = 25 },
    "", "", "/click FrostNova", ""
},

NovaSequence4 = {
    reset = { seconds = 25 },
    "", "", "", "/click FrostNova"
},
Normal Macro (Mage 1)
Code:
/click NovaSequence1
Normal Macro (Mage 2)
Code:
/click NovaSequence2
etc.

All the normal macros should be bound to the same key.

@legality - MacroSequence has been around for quite a while without issue, and it is from Cogwheel who is one of the UI & Macro forum MVPs (whatever Blizzard calls them -- green posters). It's all in-game code, and it's not doing anything that violates the spirit of the TOS either. IMO it is fine, but you should decide for yourself.

@wowphreak - Thanks for the AHK tip! It is a bizarre little language...