I find that statement a bit confusing then, you said Rumble's Flamespitter, even without Overheating, does more damage than Anivia's Glacial Storm, but also that Glacial Storm does more damage than her Frostbite, which chilled, does more damage than Flamespitter.
So, Glacial Storm < Flamespitter < Frostbite (Chilled) < Glacial Storm?
This math doesn't seem to add up. If what you are saying is true though, Anivia's kit allows Glacial Storm to be more powerful than Rumble's Flamespitter than simply looking at numbers and trying to compare one to one.
I should also note, Rumble cannot cast more than two spells, three if he manages his heat perfectly, while Overheating. This prevents Rumble from using an Overheating Flamespitter twice in a single rotation along with a shield, while Anivia can use Frostbite (Chilled) every time it is up along with her other abilities.
Overall, looking at both Anivia and Rumble, Anivia looks like a stronger champion until very late game.
Several good times to beat on Rumble:
Pre 3 - When rumble doesn't have both his shield or Flamespitter, he will try to avoid fights by farming with his harpoons, a prime time to try and force him out with an early gank.
Late Game - This depends more on the Rumble you are facing, if he is building tank with some damage, treat him like Tank Meta and build accordingly. If he is building pure mage, you should be able to pop him with some good CC lock down.
A good tactic in general is to flank him so he can only Flamespitter one of you at a time, with all the dashes in League now, that shouldn't be as much of a problem.