Starmie is always a difficult competitor to fight, and is one of the most overused water types in competitive battles because of it's high Speed and Special Attack.
In game, things are a bit different. Level beats all, as they say. Pikachu is a good choice, but since it has low defences, it can't stay in the fight forever. A good grass type - Oddish or Bellsprout, depending on your version - around L20+ with a Grass move will have marvellous advantage, including being resistant to water. Beedrill is also a good choice with Twineedle for Starmie's Psychic type weakness.
Plenty of ways to beat her. Just pick one or more, and go for it.