Also, Gyarados can learn Earthquake and Charizard can learn Earthquake, Rock Slide, and even Focus Punch; all of which are super effective against Electrics. That covers their weakness very well, but Electric types are also fragile and Charizard and Gyarados pack enough punch to defend themselves. It's a worry for Gyarados mostly, though. I think Charizard can take a T-Bolt with his 2x weakness (not saying he'll be in good shape, but at least he'll be able to retaliate with a super effective EQ or Rock Slide). Gyarados with it's 4x weakness may not be able to take the hit, and it's Intimidate won't work on special attacking Electric types.
Anyway, in my LeafGreen, I use both Starmie and Lapras on my team. If you want to use Lapras/Gyarados, then that'll work fine too. Lapras and Starmie share a lot of the same move pool, aside from Starmie's Psychic attacks and Recover. But Lapras can learn the likes of T-Bolt, Confuse Ray, Thunder Wave, Ice Beam, Surf, Toxic, and also adds the physical attacks that Starmie lacks.
But with my team, I have no Psychic or Electric types like you do, so we're in different positions. I use Lapras as my primary Water and primary Ice type, and I use Starmie was my primary Psychic, secondary Water, and opposing Water counter (I have no Electric or Grass types, so I use Starmie against other Water types because it has T-Bolt and isn't weak to Water). If you use a Starmie as a Psychic while also having a Kadabra, it'd be a waste because what Starmie does Psychically, Kadabra does better. If you also have a Lapras or Starmie as Water types while also having Gyarados, then you'll be doubling up on Water types while not being in dire need of their secondary typing. The only main difference is Ice Beam from Lapras/Starmie, but other than that they don't add much type coverage that Gyarados doesn't handle. So Kadabra and Gyarados throw a wrench in there.
My suggestion, and you may be doing this, but use Gyarados as a secondary Water type. Lapras will take that primary Water role with Surf, Ice Beam, T-Bolt/T-Wave/Toxic, Confuse Ray/Refresh. In fact, not even having a Water type attack on him at all should be a possibility, but Waterfall is handy and I can't think of anything else. Use him as a Physical Sweeper. Dragon Dance, Earthquake, Waterfall, Double-Edge/HP Flying/HP Rock.
Also, did somebody say Lickitung? I had a shiny Lickitung! /shameless brag...again!