I never really had a problem with Winona, I had more problems with Norman. Since I'm not really a fan of Fighting types (except for Mienshao which hadn't been introduced at that point) I never really had anything that powerful against his Slakings.
http://www.youtube.com/user/Shrooboid313?feature=mhee Please check out my YouTube channel. I do game walkthroughs.
In my current playthrough of Sapphire, I had more problems with Norman than with Winona. My team is always evenly leveled with the current Gym leader, meaning I had to face Norman's fully evolved team with Combusken. Worked out well thanks to Bulk Up, except his Vigoroth outsped and triple critted my bulked up starter.
For Winona, I had to resort to Rock Tomb, since my Blaziken had no Slash yet and I derped out and didn't get Icebeam for Crawdaunt(thought it was only accessible with Dive). I was really lucky since Altaria decided to just keep dancing(probably because Rock Tomb set its speed back to normal everytime). With Ice Beam and the water type you should have by that point, Winona really is a joke tough.
It was easy. Swampert at half health just kept Surfing. I don't know why but Altaria kept using Dragon Dance and It killed Swampert at barely enought HP and then voila! Manectric finally comes out. The reason may be the overleveled Swampert but he did fight through all her other pokemon