When looking back at the first trailer that Brawl had when it was first shown, it showed off a few veterans, aka, Mario, Link, Kirby, and Pika. It then showed that Pit, ZSS, Wario, and MK (forgot bout Snake...) were newcomers. They did the same thing with Melee with a few veterans first, then some newcomers in a different fashion. If Nintendo were to go the similar route, they'll have the Smash4 Trailer show some veterans fighting it out first, and then have a few newcomers appear, and most likely, another 3rd part at the end, which has been said already.
When looking at the Nintendo games these days and a bit back then, I would say that Bowser Jr and Lady Palutena are 2 of the more-likely newcomers to be shown, but I'm not certain about who else. A pattern I'm trying to figure out is what characters have potential, seem popular and believable, have importance to either Nintendo (ROB was back then I think) or to the games they're in while being very likely, but stuff like that is hard to predict when there's no trailer yet, but we'll see.