#4 seems worth exploring, and it clearly has you and others excited. Without knowing more details, it's hard to foresee what the drawbacks are going to be. Though #1 has drawbacks, I think they are solvable. Theming the experience to start at a tavern where mercenaries are available could help.
To throw in an idea, rather than unlocking the characters, have the player hire them per game. Naturally a few starting character are always free. The characters available to hire could also alternate from game to game.