Replacing Shaymin with Breloom does sound good. For move-set, my recommendation would be Spore, Leech Seed, Substitute, and Focus Punch. If it's got Poison Heal ability (or something along the lines), you should also consider giving it a Toxic Orb. This set is more for competitive side of things, but it would surely make things a piece of cake for you when it comes to defeating Elite Four and Champion.
Also, what attacks does your Gyarados have? If I were you, I'd personally go with Dragon Dance, Waterfall, Stone Edge, and Earthquake; with this, you'd be able to sweep any of your opponent within just a blink of an eye.