Megalon, I think could have replaced Hedorah, Kumonga, or Kamacuras, really. Any one of them. As much as I like the character of Monster X, as do friends of mine who aren't even Godzilla fans, I think the final monster should have been King Ghidorah, powerfull, evil, King Ghidorah.
I would have rather had the final fight be a side v. side brawl: Godzilla, Mothra, Rodan, King Caesar, and Anguirus vs. King Ghidorah, Gigan, Megalon, (fill in others).
That would have been a proper send off for Godzilla, giant Kaiju warfare.
I think the inclusion of Zilla was nice, but was unnecessary, they could have used Gorosaurus, Baragon, or Varan for that.
MechaGodzilla (whichever) would have been cool, but he'd have to be established early in the movie, if it wasn't the main villain.
And I think the Heisei 3 just wouldn't have fit in the movie, because each of them requires a good amout of backstory, it would have taken too much time out of the movie like this.