I wrote a guide for the gods, which is downloadable from
this thread, and it includes pros and cons for them all. It doesn't say "this god is for early game, this one is for late" and so on, but it gives some generalizations. Personally though, if I were to say where each god is useful, it'd be the following list. For reference, "early" means pre-rune, mid means lower dungeon/able to get runes, late means post 3-rune/Zot/extended.
Ashenzari: Mid/Late (You'll want to frequently upgrade your gear early on)
Beogh: Early/Mid (Maybe on Early. Orcs are good followers, but they lose steam later on)
Chei: Mid/Late (Gotta build piety and find good stuff for ponderous to be useful)
Elyvilon: Early/Mid/Late (Pacify early threats, great heals and buffs for later)
Fedhas: Mid (Lack of fruit early, lack of piety late, and plants lose steam)
Jiyva: Mid/Late (More so late. Once you have some decent stuff and plenty of junk around, as well as bad mutations to ditch, then Jiyva becomes useful)
Kiku: Early/Mid (Once he gives you Necronomincon or Pain Brand, he doesn't do a whole lot. Also, no piety in Tomb and Crypt)
Lugonu: Mid (Not too useful to a lowbie, dangerous even. No piety for demons.)
Makhleb: Early/Mid (Unpredictable abilities that diminish in usefulness. Healing for kills can come from other gods.))
Nemelex: Early/Mid/Late (With careful use and manipulation, decks are just that handy)
Okawaru: Early/Mid (Decent abilities, but you mostly want him for his free junk)
Sif Muna: Early/Mid (Staff of Channeling can trivilialy replace her main draw after you got the spells you want)
TSO: Mid/Late (Or just late if you kill Crypt before swapping. Piety is a PITA pre-Crypt to get and TSO's benefits primarily help against late game threats)
Trog: Early/Mid (Lack of magic really starts to hurt later and BIA, while strong, lose a bit of steam later.)
Vehumet: Early/Mid (Moreso Mid. Once he gives you his books and you can cast the spells reliably without his boosts, all Vehumet gives is mana for kills, which, while helpful, isn't a big deal and can be found elsewhere as well as a small boost to range.)
Xom: Whenever he feels like it. ('Nough said)
Yred: Early/Mid (Piety is a PITA to get in the late game.)
Zin: Early/Mid/Late (Piety is a bit of a PITA early on, but Recite pwns Orcs who make up a significant chunk of the early game threat. Later on gold is plentiful for piety and he has some very nice abilities)
Keep in mind, these are all just my opinions. Pretty much every god is useful in the mid-game, which is the largest chunk for most players. Fedhas, Kiku, Lugonu, and Yred all have piety issues that make them very difficult to worship in the late game. Beogh, Fedhas, Makhleb, Oka, Sif, Trog, and Vehumet start to lose steam as the game goes on, but are all pretty playable in the later game. They're not the best options, but they work (except Fedhas who has the piety issue too). Ash, Chei, and TSO have conducts that make the early game a bit rougher without much benefit in return. Lugonu's abilities, while powerful, are can be just downright dangerous and potentially fatal to a lowbie follower.
Personally, I think the biggest priority would be to tweak the piety/conduct gains of Fedhas, Kiku, Lugonu, and Yred so they can maintain piety much better in the late game. The gods with early-game conduct piety issues isn't as big of a deal because they just suffer from lower piety gain, not general piety loss. Balancing the abilities of all the gods not useful in early or late would be the trickier part and less important since all the gods have some usefulness everywhere with their skills. Some excel in some areas better than others, but gods like Trog and Vehumet are still perfectly feasible to follow late game.
The best strategy most frequently overlooked by new players for surviving: not starting a fight to begin with.