Zekrom with Earthquake, Superpower, Self-Destruct, Explosion, Brick Break, Hammer Arm, Flamethrower, Body Purge/Rock Polish, Trick Room, Roar, Doom Desire, Iron Head, Drill Liner, Gravity, Iron Defense, Recover, Focus Punch, Counter, Heavy Bomber, and Bulk Up.
Reshiram with Psychic, Psycho Shock, Extrasensory, Future Sight, Windstorm, Tailwind, Air Slash, Sky Attack, Thunderbolt, Roost, Earth Power, Mirror Coat, Featherdance, and Whirlwind
Re-Typings: Shibirudon as a WATER/Electric. (I seriously think they made some sort of programming error here, it's just so blatantly obvious. It would make Shibirudon much a much better Pokemon, too.
Also, Desukan as a Ghost/Steel with Levitate (Ghost/Rock works ok too). Arguably the best defensive typing in the game with that combo, and it makes more sense asthetically as well.
Gallade with Agility, Mach Punch, Sacred Sword, and possibly Extremespeed
Snorlax with Slack Off
Zuruzukin with Sucker Punch and Beat Up
Sableye with Destiny Bond (with Mischievous Heart...Priority Destiny Bond ftw!)
Doryuuzu with Stone Edge (seriously wth? it gets rock slide by level up!)
Wargle with Roost
Tsunbear with Waterfall and Earthquake
Shiftry with Leaf Blade, Night Slash, Air Slash, Wind Storm, and Whirlwind
Regice and Registeel with Recover. Not sure about Regirock...maybe Slack off? lol
Porygon-Z with Vacuum Wave
Octillery with Hydro Pump. It learns flamethrower and fire blast, but not this??
I've thought about this exact thing for years, so I have quite a few ideas. I've mainly theorized about stat changes, but I'll just post new moves for now.
Marowak with Head Smash
Aerodactyl with Head Smash and Brave Bird
Ampharos with Tail Glow (yes I know the Japanese translation, it should still get it)
Garchomp with Dragon Dance and Extremespeed (Flygon too probably)
Clefable with Swift (stars, and it's from the moon...)
Steelix with Coil (and higher Hp and Atk dammit! it's a gargantuan steel snake!
Sazandra with Nasty Plot and Pursuit
Nattorei with Rapid Spin, Earthquake, and maybe Toxic Spikes. (Forry would be utterly replaced if it got all three I think)
Kirikizan with Close Combat
Emboar with Belly Drum and Focus Punch
And the Obligatory Flareon with Flare Blitz of course. We should really sign a petition for that one. Also seconding Entei with Earthquake and Superpower, Pidgeot with Extremespeed and the rest of the suggestions from the previous posters.