Water types are everywhere and Flying types are fairly common as well. Plus, it's the best way to take down Gyarados without using Celebi and Grass not and gets unresisted coverage with Ice (another amazing attacking type) except on Magnezone and Volt Absorb Lanturn. Why do ask all of these silly questions? Why not just try these things out and see if they're any good and if they are, post them in the New and Creative Movesets Thread?
All Pokemon that can learn TMs besides Regigas can learn Rest and they aren't Psychic. Agility often has more to do with high speed than being Psychic and other moves are like this too. For example, all Electric types can learn Light Screen and many Fighting types can learn Meditate. I'd run ThunderPunch because Gliscor can be hit neutrally by Meteor Mash and is countered fairly easily by Bulky Waters and Zapdos gets hit SE by Stealth Rock. Rotom-A is annoying but Zen Headbutt seems more like a liability to me than it's worth.