An Ultimate Magus would be an interesting possibility for jqavins suggestion. It might not be the best option when it comes to raw power though. He should have a good measure of wisdom too, based on his former career as a Cleric.

As for why Arkis has lost his divine spellcasting abilities? Have you ever heard what happened to Prometheus after he stole fire from Olympus and gave it to the humans? Losing your divine spellcasting wouldn't be half that bad compared to what happened to Prometheus.
Another option would be that he lost his faith when he learned that the god of knowledge was keeping arcane magic a secret. He could also have ascended to godhood which makes the whole being divine spellcasting thing obsolete. (Except if you use the rules in deities & demigods, I think. So meh.)

Honestly though, I'd stick to the Greek tragedies. The gods would either kill Arkis or make an example out of him. Turn him into some hideous monster or something. A lich would fit, or maybe a dragon.