Trog really is a very good choice for trolls. There are few things more frightening than a berserking troll, and Trog can see to it that you carve your way through veritable hordes of orcs and gnolls with his ability to sustain your rage over longer periods. And the Hand of Trog ability makes an already fearsome regeneration become downright insane. Furthermore, trolls will never, ever have a use for spellbooks, so there's nothing to lose from torching them. And Trog's abilities don't cost MP, which is excellent since trolls have absolutely abysmal MP and intelligence scores.
However, Trog's gifts don't usually do a whole lot of good for trolls, as most trolls will just use their hands to carve their way through most things. You can try training up your ability to club stuff, but as with any other sort of trollish skill beyond unarmed combat, it's going to be an uphill battle. You may want to switch over to clubs later on anyways, for various reasons.
Unfortunately, Trog likes sacrificed corpses, and as a troll you'll probably be eating a fair portion of them. In some infested places like the orc mines you should have enough bodies to spare sacrificing a number of them, but you're still not going to be able to offer up as much as other, less hungry races.
Trog isn't the only choice for trolls, however. If you're willing to go a slightly trickier route, Nemelex Xobeh can offer some magical diversity for your trolls with card gifts. You'll be able to get lots of destruction or escape decks due to mass weapon/armor sacrifice, but summoning decks will likely be few and far between. I think Nemelex's abilities might cost some MP however, but they're not exactly necessary. Getting evocations up to a respectable level will be utter torment, but it does give your troll a bit more versatility.
A slightly more off-the-beaten-path choice would actually be Kikubaaqudgha. Although Kiku is primarily geared towards necromancers, non-spellcasters can get some interesting gifts from him as well.
First of all, protection from torment is always nice to have, and Kiku is one of the best for that. Second, Kiku doesn't care about corpses, he only wants stuff to die. This is perfect for a troll, as you get to keep the little munchies all for yourself. Third, at higher piety levels Kiku will cast torment for you if you pray over a body.
Now, let's just think about that for a bit... Can you imagine dragging a corpse down into the orcish mines, and then shredding the orcs down there with a god-sent torment that you are shielded from? And now instead of being a weakling spellcaster, you're a sodding troll, and you're far more than willing to capitalize on the now-weakened state of the nearby fleshbags.
Kiku also has one very interesting ability that was designed to help necromancers but can actually give a unique and highly valuable boost to trolls. At higher piety levels, you can call upon Kiku to send a number of corpses (size and number dependent on invocations) to your location.
Normally, trolls are hindered from even thinking about going into certain food-scarce areas that are filled with demons, undead and other corpseless nasties. With this ability, you can just call on Kiku when times are rough and he'll grant you a nice snack to keep you going. The piety cost is a bit nasty, but with any luck you should be able to slaughter enough stuff to restore it by the time your hunger runs down again. Do note, however, that the corpses provided are random and potentially harmful... Kobolds, necrophages, brain worms and more have popped up in corpse piles. While you may get the occasional giant to chow down on, this ability is by no means a certainty. Higher invocations levels will up the number of corpses, thus increasing your odds of finding something tasty.
Kikubaaqudgha can also grant a permanent pain brand to a weapon, but this really isn't very useful for a troll.
Beyond that... Well, Cheibriados can help you out a bit. Trolls can't wear most armor, so the ponderousness brand can help give you some defensive help. Che will also slow your metabolism and give you some powerful magical abilities that can shred certain monsters, but his abilities tend to have a rather high MP cost.
Elyvilon isn't much help with her healing (you've already got that pretty much covered), but damage shielding is always nice and she can help cleanse your system when you eat something particularly nasty. Also, you'll be able to sacrifice plenty of weapons for her due to your "hands-on" approach to things. Also also, neutrality to holy beings is pretty dang nice in some situations. Invocations skill is kinda necessary though, which can be problematic.
Jiyva can give you some nice mutations and abilities, and you won't be as reliant on items as other species so there'll be more stuff for the jellies to chow down on. Stat shifting can potentially be dangerous though.
EDIT: Makhleb wouldn't be that great, as all his abilities rely on invocations and MP, two areas that trolls are fabulously bad at. Makhleb works for characters who want some spell-like abilities, but are still allowed to wear very heavy armor (which really isn't an option for trolls anyways). And, again, the corpse sacrificing issue.