The Redwall Character Guide
To me, reading though the history of many different characters is a painful and excruciating business. Why? Because they're all the same. I'll give you an example, with a fictional otter named Bob.
It was in his infancy that Bob became orphaned. His home, where his peaceful parents lived happily, was attacked by a band of evil raiders headed by a stoat named Jack. Bob grew up planning vengeance. He became strong, and handsome. He began to hunt through the country side, hoping that one day he would catch up with Jack, and finally pay the stoat back for the harm done to Bob's family.
Have you ever noticed…
That "vengeance" and "revenge" aren't the only conflicts a character has? I hope so. If not, you can either take my word for it that they're not the only conflicts, or you can realize it yourself. There are a lot of conflicts and histories that aren't so "vengeance" and "revenge" oriented. Take a look at a few? Glad you suggested it.
This one is easy, fun, and interesting. Always good, too. It's a character that is supposed to become one thing (normally something their parents planned for them, or something they have to become one way or another), but who really wants to be something else. For example, someone who's supposed to inherit and run their father's woodshop but really wants to become a warrior. Or someone who is a warrior, but just wants to make and run a woodshop. It can go any which way you want.
The Cast Off
This is also pretty easy, and a bit easier than the other one. It's actually a lot like the other one. It's a character that was in a position of power and goes to a position of absolutely no power. It's used a lot in stories, too. Especially ones where the hero learns humility.
The Quest for Immortality
I have to include this one because it's used so much in literature. A quest by anyone for immortality is always a good reason for anyone to do anything. The only sad part about this is that they won't ever be able to get immortality.
Don't let this list limit you, though. There are a lot of other things you can do. Spend a day or two thinking of interesting stuff for your history, or for it's personality, flaws, or quirks.