I think it might be hard to make it worth the effort.
But it's still a very nice idea. One way I could see it work would be to make different background stories that doesn't depend on class or even race necessarily. That way you simply choose the one that fits best to your character. But for it to make a difference it should have an impact on the game any or all of:
Small bonuses. such as skills, starting money or reputation.
Certain extra options. For example, if you started as a sailor instead of choosing between saving the your drowning friend or stopping the evil sea creature that stole from you, you can do both.