Wow this is fun!
here are some more, I'll also try to add some that are obviously female to aleviate the gender balance a bit (though of course it's possible if the battle text could indicate the gender of participants you wouldn't specifically need female sobriquets, e.g Red Sonja and Halthris the Tenathi from Pamela Bell's silver city series (probably the best written female barbarian character I've ever read), don't have specifically feminine titles.
Anyway on with the suggesting:
suffixes:
Of the hill,
Of Stony hill,
Of the wild hills,
Of the red hill,
Of the green hill,
Of the barron hills,
Of the long hills,
Of the north shore,
of the south shore,
of the east shore,
of the west shore,
Of the wild shore,
Of the black shore,
of the pirate shore,
of the far shore,
of the farthest shore,
of the last shore,
Of the cold shore,
Of the troll shore,
Of the deepest shore,
Of the utter shore.
Goldilocks,
Sunhair,
Raven haired,
Winter maiden,
ice maiden,
snow maiden,
Frost maiden,
Sand maiden,
Blood maiden,
handmaiden,
the fair maiden,
Death's hand maiden,
Chaos maiden,
The shield maiden,
The sword maiden,
The courtesan,
The Hoar,
the Geisha,
The chamber maid,
The housemaid,
the maid,
The housekeeper,
Miller's daughter,
Miller's son,
Farmer's daughter,
Farmer's son,
Blacksmith's daughter,
Blacksmith's son,
Baker's daughter,
Baker's son,
Piper's daughter,
Piper's son,
The piper,
the baker,
the miller,
The Wolf,
The ravening,
The reaver,
The pirate,
the iron pirate,
The iron captain,
The steel captain,
The black pirate,
The red pirate,
The famous pirate,
The oak hearted,
The iron hearted,
The cold hearted,
The black hearted,
The kind hearted,
the pleasant,
The nice,
The polite,
The unpleasant,
The extremely unpleasant,
The really extremely unpleasant,
The really quite seriously extremely unpleasant,
The nasty,
The highly nasty,
the not quite so nasty,
The lame,
the limping,
the halt,
The blind warrior,
the blind bandit,
The blind monk,
The unarmed.
The ugly,
The plug ugly,
The pug fugly, (okay I admit that one is a bit of a joke),
The foul smelling,
The sweet smelling,
The gardener,
Tree lover,
Silver, (as in long John silver),
The homeless,
The vagabond,
few clothes,
Bear shoulders,
iron grip,
bear claw,
Of the heavy hand,
The hammer hand,
Black stone,
Green stone,
Blue stone,
Elf stone,
Vampire stone,
blood stone,
Chaos stone,
Shadow stone,
Shimmer stone.
The boar,
The wild boar,
The elephant,
The learned,
the scholar,
The wise,
The crone,
The falcon,
The eagle,
The eagle eyed,
The keen sighted,
The hawk,
the black bird,
the kestrel,
The vulture,
The crow,
gore crow,
storm crow,
The bloody,
The bloody axe,
the thorn,
The black thorn,
The rose thorn,
the phoenix,
The cold,
the cruel,
The unkind,
The ungentle.
The Gentle,
And here are some prefixes, note that some things such as furious can be both a suffix and a prefix, e.g you could have furious jo, as well as jo the furious, and farmer bob as well as bob the farmer. Plus this is a way sneak discripters as in "boy billy" or "man friday"
Long,
short,
tiny,
tall,
big,
Furious,
curious,
hideous,
hairy,
smelly,
sweet,
daft,
mad,
big mad,
Big mad hairy,
deadly,
merdurin,
boy, (
girl,
man,
thin,
Starving,
Desperate.
fat,
gross,
beautiful,
dangerous,
beloved,
And methinks I had better stop there 
.
With our dreaming and singing, Ceaseless and sorrowless we! The glory about us clinging Of the glorious futures we see,
Our souls with high music ringing; O men! It must ever be
That we dwell in our dreaming and singing, A little apart from ye. (Arthur O'Shaughnessy 1873.)
