Trolls are ubiquitous in FRPGs. Just go to Chapter 2 of The Hobbit and you will see why.
The trouble is they are so ubiquitous that they often get forgotten as a real threat. Not surprising really. When you live in a world of dragons, demons and other horrors, the simple troll can seem, well, quaint.
Well they shouldn't be. Trolls were once the "demons" of the world. They were the monsters.
To help us remember that there is a new film out of Norway (where Trolls still sleep) called "Troll Hunter"
And here is one of the trolls,
That's a troll worthy of your characters.
I have always preferred the the more Scandinavian Troll over the green rubbery one from the Monster Manual. I like trolls that look like they are made out of rock and earth. So for that, here is the Troll I have used in Basic Era format.
Armor Class: -1 
Hit Dice: 10d8* (50 hp)
No. of Attacks: 2 claws / 1 bite
Damage: 1d6 / 1d6 / 1d8+3
Special: Darkvision 90 ft., regeneration, vulnerability to sunlight
Movement: 30 ft., burrow 40 ft.
No. Appearing: 1 (1-3 in lair)
Saves: Fighter 10
Earth Trolls are relatives of the normal troll and make their lairs deep within the subterranean realms of the earth or in dense forests where the sunlight is easily avoided. Most creatures avoid Earth Trolls, as they are completely malign and evil, attacking any living creature, especially when hungry. They are quite fond of humanoid flesh and usually stage raids upon surface dwellers every month. Because of this, they are often encountered in large surface caves in the sections well outside the reach of sunlight.
Earth Trolls are 10 feet tall and weigh about 1,200 pounds with females being slightly larger. They resemble their smaller relatives in most respects, but some accounts have them appearing as rather large and misshapen gnomes. The Earth Troll’s hide is stone gray or brown, its hair is black or brown, and its eyes are dull brown. Like its counterpart, the Earth Troll’s arms and legs are long and thin. Its arms end in sharpened talons, and its legs sport great three-toed feet. Earth trolls will attempt to dress or adorn themselves in whatever rags, hides and bits of clothing they can find.
Earth trolls are a little smarter that their more common cousins. While they still do not have concept of strategy, they are smart enough to speak and to use some simple weapons.
Earth trolls speak the language of all trolls, some have been known to speak orc or goblin as well.
Earth Trolls attack any living thing that enters their territory, usually doing so for food. They will band together for very simple ambush tactics but that is about the extent of their strategy and planning. Most of the time an earth troll will flail relentlessly at its foes with its powerful claws until either it or its opponent is dead, but some have been known to use a large club and others even a spear or sword.
Regeneration: An earth troll heals only if it is underground and touching dirt or earth. If in contact with the earth it heals 3 hit-points per round. If contact is lost, say the troll is levitated or flying, then the healing stops. Trolls turned to stone heal hit points (but not lost limbs).
Vulnerability to Sunlight: An earth troll exposed to natural sunlight (not merely a spell or magical item that replicates sunlight) is instantly turned to stone (as if by the flesh to stone spell) if it fails a Petrify save. This effect is permanent, but can be dispelled if the earth troll is removed from the sunlight and stone to flesh is cast on it.
Section 15 Copyright Notice
Open Game License v 1.0a Copyright 2000, Wizards of the Coast, Inc.
System Reference Document Copyright 2003, Wizards of the Coast, Inc.; Authors Jonathan Tweet, Monte Cook, Skip Williams, Bruce R. Cordell, based on original material by E. Gary Gygax and Dave Arneson.
Liber Mysterium: The Netbook of Witches and Warlocks is Copyright ©2003, Timothy S. Brannan and the Netbook of Witches Team.
Basic Fantasy Role-Playing Game Copyright © 2006-2008. Chris Gonnerman.
Labyrinth LordTM. Copyright © 2007, Daniel Proctor. Author Daniel Proctor.
"Earth Troll" Copyright ©2011, Timothy S. Brannan