Point 1: There's nothing inherently stopping you from starting with 13 warriors. They don't necessarily have to follow the player party. During part 1 your group of 13 warriors might split up to guard two or more parts of the town. This gives your player party one or two red shirts for that fight. It's probably more work for you to play those on top of the enemies but, you can...
Point 2: Nothing dictates that a "warrior" HAS to be a barbarian class melee fighter. If you say that your setting has all kinds of fighting styles and classes then it does.
Point 3: There's nothing saying that your players have to be ready for the adventure when it begins. Particularly if you fill the party up with higher level NPCs you could definitely give your players the same "arc" as the protagonist had. Starting inexperienced before growing into themselves and becoming an integral part of solving the problem. Might require some behind the scenes fudging of rolls until they catch.
Another idea would be to start ALL 13 characters somewhat underleveled and when a player character dies, they get one of the remaining ones to continue.