Since i dont play the cartridge games, i dont know how time consuming it is to change your EV spread... but if its not a huge hassle then i happen to know a zapdos set that works very well, its called SubRoost Zapdos
176 Speed EVs lets your Timid Zapdos outspeed all lucario
Then you want to put the extra 76 EV points in HP for a little more bulk.
Using a bulkier Zapdos can help tremendously with your gyarados problem as well
Someone else might have a better EV spread...