Hey WMBQ, about your team, I know I'll sound incredibly lazy about this, but.. You could level grind Charmeleon a lot, and it'l definatly OHKO Staryu with Mega Punch. Starmie will probably be a 2HKO - if Charmeleon's a high enough level, it won't be OHKO'd. Brute force solves a lot of things. XD
For level grinding, if you havn't already, there's the nugget bridge and the trainers above. Do you have the vs. seeker yet, btw? That'd certainly help.. I can't remember when in the game you get it, though.
Storm's brilliant Oddish idea is also reliable. Oddish evolves at level 21 btw, so Gloom would rip Staryu and Starmie to shreds with Mega Drain(which is learned at lv. 21 right before it evolves, btw). A gloom isn't that bad of an addition to your team either, right? Especially once you find a leaf stone.
Sorry for being such a lazy n00b Mega Luigi, but here's a link to Deoxys-A's Smogon page. The first Life Orb set is what you'd want, standard epic Deoxys-A. It's exactly what I'd recommend anyways. I'm sure it's what you'd want, after all.