First off, just throwing it out there- there is no rules as written way to get divine ranks. (In core, anyway.) Which means we don't have any other method we need to balance with or to use as a guideline.
So, how powerful is a divine ranked character? I would contest the claim that epic spellcasting is strictly superior to salient abilities, and gods get way more than just that. Just pointing it out- one of the possible abilities is "Alter Reality... Benefit: This ability is similar to the wish spell. The deity merely thinks of something and then makes it so. Doing this requires at least a standard action." The ability to cast Wish as a standard action, unlimited times per day, with no XP or materials cost, is somewhat hard to beat. Not saying that epic spellcasting isn't potent. Oh, and there's also the option of Arcane Mastery... Benefit: The deity can prepare any wizard spell that it can cast without using a spellbook... The deity also can invent new sorcerer/wizard spells without researching them." This is still ignoring the other, general abilities gods get. Little stuff, like DR 15, immortality, senses out to a mile away, literally always get a 20 (Though not always a crit, thank heaven for small mercies) on every single roll, and cast Greater Teleport as a spell like ability at will.
This is a small subset of the powers that a character with a single divine rank would have. I'm not sure offhand how many levels a character would have to accrue before gaining one. Offhand, I'm going to go with "Lots" and leave it at that.
However, that doesn't actually answer your question.
First, this should be a quest. Not something your players just get when they level up. They should kill a god, or aid a god tremendously, or save the world twice. Something suitably epic. Then, I would give them all divine rank 0, and increase that rank separately from when they level. Let them keep leveling up as they normally would, but grant them all additional divine ranks whenever they accomplish something particularly impressive. If it helps, a divine rank 1 god has a few thousand mortal worshipers. It works perfectly fine to have the party/pantheon as a whole be worshiped, and gain ranks together, as the pantheon gains followers. Such increases have little to do with a character's level, though they can still use their regular powers as they want, probably augmented with their divine powers. What powers they have is fairly well proscribed by the rules, just not how to increase them.
As for homebrew methods to increase these ranks, here's a few ideas.
Treat each divine rank as a level. (Tracked separately from regular levels.) They only get divine XP for defeating opponents with divine ranks. Use the regular XP/Level table to determine how much divine XP is needed to level up the divine ranks.
Treat each divine adventure as a rank obtained for defeating a higher tier of foes. Have them slowly fight, trick, and connive their way through the older ranks of gods. As each tier of gods falls- they step in to fill the space.
Use the amounts of worshippers as a way to gauge it. Have them (by hook or by crook) find ways to increase the number of mortal worshippers.
Just be aware- challenging these divinely powered individuals is going to be interesting. I'd look at this question for help with that.