I think with some vague trickery it's possible to have unlockable characters.
As for custom storylines, of course! I have this idea that I've been wanting to bring to life for a while, but I can't see the harm in telling you about it. You can start with a map that determines if you're using Sonic, Tails, Knuckles or "none of the above" by using intangible FOFs, custom exits and no-x-character flags. Then you have a version of the maps for each character that plays a different cutscene (and maybe even have different layouts). You can also do multiple story paths this way.
Just be aware though. Not many people are going to care for your story if you make it too ridiculous and the cutscenes too long-winded (it's happened many times before), so be humble about it, and don't let the cutscenes detract from the action too much. Consider having (minimal) story dialogue during the levels if you have a lot to convey at any given time. In short, less is more.