Well, if you guys are really adamant on not sacrificing characters in the prologue, there's only two ways I know around it. You can kill Gordin since he's considered an enemy (unless Marth talks to him), though I guess that kind of means you sacrifice Gordin, and you'll be without a bow user until the second chapter (unless you get Norne). Or you could play hard mode and skip the prologue altogether. Frey won't be there though so that kind of means he got sacrificed. Also, Hard Mode on Fire Emblem games is brutal since the enemies are so much stronger than you. There's different Hard Mode difficulty levels though so I guess you could choose one of the easier difficulties.

I've also finished my second playthrough, where I didn't stay to the original since I used the Reclass system, I used every character that wasn't in the original, and I completed all of the sidequest chapters (too bad you have to kill off a lot of your characters to access them).

I guess I'll explain Reclassing more. Basically, characters that are class changeable belong in either two groups, the Pirate-Mercenary-Fighter-Dark Mage-Knight-Hunter Group or the Cavalier-Pegasus Knight-Archer-Mage-Cleric-Myrmidon Group (the upgraded versions of those classes are also in those groups). Cavaliers are specifics to males and Pegasus Knights to females (don't ask how Medea is an exception to that since I don't know either). Any class that can change classes are restricted to changing into classes in their group, so a Mage can change to a Cleric, but not a dark mage. You're probably also wondering how fighting classes are when they change to magic classes. From my experience, they're okay, but their magic stat is quite low and their strength is usually higher than their magic, despite being magic casters. You kind of have no choice but to make one of your physical fighters a dark mage though (unless you're willing to kill off a bunch of your characters to do the side quests so you can get one that's already upgraded). I don't there's any problems making a Mage into a Cleric though or anything like that. I changed one of my Knights into a Pirate and he turned out great so I'd assume it's the same for magic classes. Also, I'd highly recommend against changing Shiida into anything else. Her being a Pegasus Knight makes it really easy reaching recruitable enemies and converting them before they reach your characters (and she converts a lot of characters). She also has the Wing Spear which is powerful and usable only by her, and she can't use it as any other class (unless you cheat and make her a Knight or something).

Also, they've added travelling mercenaries to the game (don't confuse these with the Sword fighting mercenaries). If too many of your characters die, you'll get some new characters that will join you temporarily to make up for not having many characters. They don't have any personalities or faces for that matter. They basically have the generic enemy picture for their face picture, except they're not enemies. I don't know when they leave though since I killed them off, wanting to access the gaiden chapters. They come with weapons equipped on them and they get stronger the farther you are into the game. I wouldn't recommend using stat boosting items or Master Seals on them since they'll leave anyways. I haven't seen them leave but one of the houses I visited told me about the travelling mercenaries, not knowing what he was talking about until my second playthrough.

Anyways, regarding the new characters (that have faces and don't leave you) there's Frey, Norne, Athena, Horace, Etzel, Ymir, and Nagi. Frey is a typical level 1 Cavalier that you get near the start (no need to kill off people to get him, though technically he is the one that gets killed in the original), having higher strength than Abel and Kain, though Kain has the highest luck and Abel skill. Norne you get if you complete all the prologue chapters with four or less characters. Compared to Gordin, she gets more speed but Gordin gets more defense. They're both good archers though. Athena eez vun of the few (decides to stop it with the French accent, though she does speak with one and makes Marth talk with one at one point) sidequest characters that you can get that aren't promoted. She's a good Myrmidon, though I don't know how she compares with the others like Nabarl and Radd. Horace (General), Etzel (Sorceror), and Ymir (Warrior), though they're all promoted already have decent stats, though levelling their pre-promoted forms at level 20 then promoting them will probably get you better characters stat-wise (I tried it with Draug and Barst on my first run-through). They can all still hold their own in battle though, and kill off enemies as efficiently and successfully as non pre-promoted characters, and take and evade attacks. I'd at least give Etzel some consideration seeing how he's the only Sorceror you get in the game. Even if you change someone into a Sorceror, their magic stat will be low since you always have to change someone from a physical fighting class to a Dark Mage/Sorceror. Nagi you get at the last chapter if you don't have both Chiki or the Falchion after finishing Chapter 24. She's a level 15 Manakeet who starts with a Divine Stone (enabling her to kill Medeus in two shots). She's a very good character, though getting her means you won't get Gotoh, which sucks but I guess is a fair tradeoff.

So I guess I've explained everything you're all curious about. Feel free to ask me any more questions.