Make a variant troll. How 'bout one of the following:
1) It's a rock troll. Instead of rubbery green skin, it has a stoney grey hide that looks like miniature boulders. Acid and fire have no special effect on it, but effects that break rocks (e.g. thunder, force) stop its regeneration. If the party doesn't have these damage types available, then perhaps they have to specifically target its less-protected under-belly. Damage from these attacks can't be regenerated, but it's a more difficult target; roll with disadvantage for any attack against its soft belly.
2) It's a two-headed troll, a crossbreed between an ettin and a troll. Same stats as a troll, but it loses the regeneration property, has maximum troll hit points (120 hp) to reflect its larger size, and has the Two Heads and Wakeful properties of the ettin.
3) It's a spirit troll, a magical cross of an invisible stalker and a troll. These things actually appeared in the old 1e Fiend Folio. An invisible stalker's a bit tough for what you're looking for. A low-level party is not going to enjoy a creature that is naturally invisible, especially if it does the old move-attack-move routine (meaning that it's incredibly hard to pinpoint where the creature is at any time). So, make it the misty outline of a troll - advantage on Stealth checks, but no other combat benefits. Not quite invisible, but clearly not a regular beast. Use the normal troll stats, but remove regeneration. Instead, replace it with the invisible stalker's resistances and immunities. The resistance against non-magical weapons makes up for its loss of regeneration.
4) It's a lava troll. Same as the rock troll above, but the stoney hide glows cherry-red with heat and thin lines of fire can be seen between the rocks. It is immune to fire, but its regeneration can be knocked down with acid or cold attacks. Failing that, dowsing it in a large quantity of water will also work. Cue the mad chase as the party tries to lead it to the nearby river, a few hundred feet away!
5) It's a scrag (aquatic troll; 1e D&D again), and it's covered in reeking wet mats of seaweed. It's resistant to fire and acid while covered in these rags. Lightning damage knocks down its regeneration (given water conducts electricity). If the party doesn't have lightning damage, then they have to remove its soaking wet seaweed "armor" before burning its vulnerable body with fire. They will need to grapple the creature (!) and succeed on an opposed Strength check to tear free its seaweed. This may seem like a tall order against its 18 Strength, but 2 characters can cooperate for advantage on the rolls.