I'm no expert on Tentacruel, but he walls Bulky Waters like no one's business, so HP Electric would be great for not only taking out Gyarados, but other water threats that they throw your way. Still, be wary of Electivire + Gyarados, if your opponent begins to become accustomed to your strategy.
As for me, I have a Calm Mind WoW Mismagius, and thanks to it's wonderful IVs, it has access to HP Ice. Which provides better coverage, Shadow Ball + Thunderbolt, or Shadow Ball + HP Ice? I know Electric prevents the set from being completely walled by steels, but I'm not sure how it fares against common Mismagius counters or Metagame threats.