Keep it a normal Type, since it's the most reliable. (No Dragon typing. C'mon, EVERYONE will expect a Draco-Arceus.)
Since it's a normal-type, its only weakness is Fighting, you could teach it Psychic. You can go for a Physical or Special Route, depending on how you want to use this God of a Pokemon.
PHYSICAL ROUTE:
Zen Headbutt
Last Resort
Earthquake
Dragon Claw
SPECIAL ROUTE:
Psychic
Hyper Voice
Ice Beam
Thunderbolt
Arceus has a MONSTROUS movepool, so it's quite possible I missed something important. It's easy to make a good movepool for it though. Just open that bag, and look for a TM. Chances are, he can learn it. =P
EDIT: Like Trachy said, Electric is also a great type, due to its one weakness and three resistances (electric, steel, and flying). I simply picked normal because of the versatile typing, and easy STAB for both Last Resort and Hyper Voice.