The following post is a huge wall of text. Just a heads up. So, don't try to quote the entire post.
Super Smash Bros. came out in Japan on January 1999 and North America on April 1999. This means we must assume that it was developed throughout most of 1998.
Nintendo's #1 mascot, protagonist/mascot of the Mario series, Super Mario 64 (1996), Super Mario World (1990), Super Mario Bros. (1985)
protagonist/mascot of the Donkey Kong series, Donkey Kong Country (1994), possibly advertising Donkey Kong 64 (due to come out in November 1999)
protagonist/mascot of the Zelda series, The Legend of Zelda: Ocarina of Time (1998), The Legend of Zelda: A Link to the Past (1991)
protagonist/mascot of the Metroid series, Super Metroid (1994)
protagonist/mascot of the Yoshi series, Yoshi's Story (1997), Super Mario World 2: Yoshi's Island (1995), Super Mario World (1990)
protagonist/mascot of the Kirby series, Kirby's Dream Land 3 (1997), Kirby Super Star (1995), possibly advertising Kirby 64: The Crystal Shards (due to come out in March 2000)
protagonist/mascot of the Star Fox series, Star Fox 64 (1997), Star Fox (1993)
#1 mascot of the Pokemon series, #1 star of the Pokemon anime (1997), protagonist/mascot of Pokemon Yellow (1998), Pokemon Red/Blue (1996)
protagonist/mascot of the F-Zero series, F-Zero X (1998), F-Zero (1990)
protagonist/mascot of the Mother series, Mother 2 (1994), Mother 1 (1989) through his likeness to Ninten
the second half of the Super Mario Bros., protagonist/mascot of the Mario series, Super Mario World (1990), Super Mario Bros. (1985)
purportedly the #2 mascot of the Pokemon series in Japan during the 1990's, added as a joke character, Pokemon Yellow (1998), Pokemon Red/Blue (1996)
Super Smash Bros. Melee came out in Japan on November 2001 and North America on December 2001. That must mean it was developed from late 2000 through the summer of 2001.
antagonist/mascot of the Mario series, Super Mario World: Super Mario Advance 2 (2001), Paper Mario (2000), Super Mario 64 (1996), #1 in the Mario category with 169 votes on the Melee poll
major character and mascot of the Mario series, Super Mario Advance (2001), Paper Mario (2000), Super Mario RPG: Legend of the Seven Stars (1996), #2 in the Mario category with 66 votes on the Melee poll
:shiek: in Zelda's case: major character and mascot of the Zelda series, The Legend of Zelda: Ocarina of Time (1998), The Legend of Zelda: A Link to the Past (1991); in Sheik's case: a very popular major character who is really Zelda (but not the mascot of the Zelda series because she is an one-time character) at the time Zelda 64 was still new, both were tied for #2 of the Zelda series with 8 votes on the Melee poll
mascots/protagonists of Ice Climber (1985), added to represent the Famicom era (1983-1989), #9 in the Other category with 4 votes on the Melee poll
:mewtwo: mascot of the Pokemon series, star of the first Pokemon movie (1998), Pokemon Yellow (1998), Pokemon Red/Blue (1996), #1 in the Pokemon category with 35 votes on the Melee poll
protagonist/mascot of the Fire Emblem series, Fire Emblem 3 (1994), Fire Emblem (1990), #1 in the Fire Emblem category with 21 votes on the Melee poll
protagonist/mascot of the Game & Watch series, Game & Watch Gallery 3 (1999), Game & Watch Gallery 2 (1998), Game & Watch Gallery (1997), possibly advertising Game & Watch Gallery 4 (due to come out in October 2002)
protagonist/mascot of the Dr. Mario spin-off series, Dr. Mario 64 (April 2001 in North America), Dr. Mario (1989), added only to buff the roster
major character of the Star Fox series, Star Fox 64 (1997), Star Fox (1993), #1 in the Star Fox category with 7 votes, likely added to buff the roster in the first place
antagonist of the Zelda series, The Legend of Zelda: Ocarina of Time (1998), #1 in the Zelda category with 36 votes on the Melee poll, added to buff the roster in the first place because Sakurai didn't plan to add him but eventually did so because he had a similar body build to Captain Falcon
protagonist/mascot of the Zelda series, The Legend of Zelda: Majora's Mask (2000), The Legend of Zelda: Ocarina of Time (1998), #2 in the Zelda category with 8 votes on the Melee poll, most likely added to buff the roster
ichu: #1 mascot of Pokemon Gold/Silver (1999), most likely added to buff the roster
protagonist/mascot of Fire Emblem 6 (due to come out in March 2002), most likely added to advertise Fire Emblem 6 and to buff the roster
Super Smash Bros. Brawl came out in Japan on January 2008 and North America on March 2008. It was developed throughout 2006 and 2007.
major character and mascot of the Kirby series, Kirby & the Amazing Mirror (2004), Kirby: Nightmare in Dream Land (2002), possibly advertising Kirby Super Star Ultra (due to come out in September 2008), #3 in the Kirby category with 11 votes on the Melee poll
protagonist/mascot of the Kid Icarus series, Famicom Mini Series: Kid Icarus (2004, Japan only), Kid Icarus: Of Myths & Monsters (1991, North America only), #6 in the Other category with 5 votes on the Melee poll
protagonist/mascot of Metroid: Zero Mission (2004), an update on the "Justin Bailey" Samus from Metroid (1986)
protagonist/mascot of the Wario series, Wario: Master of Disguise (2007), WarioWare: Smooth Moves (2006), Super Mario 64 DS (2004), possibly advertising Wario Land: Shake It! (due to come out in July 2008) through Wario's alternate costume and victory music, #3 in the Mario category with 65 votes on the Melee poll
protagonist/mascot of the Metal Gear series, Metal Gear Solid: The Twin Snakes (2004, I am not counting Sony's release dates), added only because Kojima "practically begged" Sakurai to do so
protagonist/mascot of Fire Emblem: Path of Radiance (2005), also appears in Fire Emblem: Radiant Dawn (2007)
Red is the protagonist of Pokemon FireRed/LeafGreen (2004), the starter Pokemon are the mascots of the Pokemon series, #3 in the Pokemon category with 18 votes on the Melee poll
protagonist/mascot of the Donkey Kong series, Donkey Kong Barrel Blast (2007), Donkey Kong Country 2: Diddy's Kong Quest (Virtual Console, 2007), Donkey Kong Country (Virtual Console, 2006), #3 in the Rare category with 15 votes on the Melee poll (he is the only Donkey Kong character on the poll, that makes him #1 in the Donkey Kong category)
protagonist/mascot of Mother 3 (2006), originally planned to replace Ness in Melee but Mother 3 was cancelled at the time but Lucas finally got added since Mother 3 was finally released
protagonist/mascot of the Sonic series, Mario & Sonic at the Olympic Games (2007), most likely added due to fan demand
antagonist/mascot of the Kirby series, Kirby: Nightmare in Dream Land (2002), possibly advertising Kirby Super Star Ultra (due to come out in September 2008), #1 in the Kirby category with 46 votes on the Melee poll
protagonist/mascot of the Pikmin series, Pikmin 2 (2004), Pikmin (2001)
#1 mascot of Pokemon Diamond/Pearl (2006), star of the Lucario movie (2005)
peripheral used to play Gyromite (1985) and Stack-Up (1985), unlockable character in Mario Kart DS (2005)
protagonist/mascot of the Zelda series, The Legend of Zelda: Phantom Hourglass (2007), The Legend of Zelda: The Minish Cap (2004), The Legend of Zelda: The Wind Waker (2002), most likely added to replace Young Link
antagonist of the Star Fox series, Star Fox 64 (Virtual Console, 2007), Star Fox Command (2006), Star Fox Assault (2005), most likely added to buff the roster in the first place, #3 in the Star Fox category with 4 votes on the Melee poll
Almost all of the characters I listed above have been playable in their native games and that leads me to the conclusion: playable characters are more likely to become playable in Smash. Another conclusion is this: mascots and protagonists are more likely to become playable in Smash, especially when their games were recently released or will be released during the Smash development. So that is why I really think these following characters are very likely and could get in the SSB4 roster.
Dixie Kong - protagonist/mascot of the Donkey Kong series, Donkey Kong Barrel Blast (2007), Donkey Kong Country 3: Dixie Kong's Double Trouble (Virtual Console, 2007), Donkey Kong Country 2: Diddy's Kong Quest (Virtual Console, 2007), Sakurai might have considered adding Dixie Kong in Brawl so there is a possibility he would want to try adding her in SSB4
Isa - protagonist/mascot of Sin & Punishment 2 (2010), Saki was an Assist Trophy in Brawl (Isa is said to be Saki's son with Airan)
"Isaac" - protagonist/mascot of Golden Sun DS (2010), Isaac was an Assist Trophy in Brawl (the new protagonist really looks a lot like Isaac but with different clothes so that's why I gave him a temporary name "Isaac" before Nintendo tells us his official name)
King K. Rool - antagonist/mascot of the Donkey Kong series, Donkey Kong Barrel Blast (2007), Donkey Kong Country 3: Dixie Kong's Double Trouble (Virtual Console, 2007), Donkey Kong Country 2: Diddy's Kong Quest (Virtual Console, 2007)
Little Mac - protagonist/mascot of the Punch-Out!! series, Doc Louis's Punch-Out!! (2009), Punch-Out!! (2009), cameo in Captain Rainbow (2008), Assist Trophy in Brawl
Mega Man - protagonist/mascot of the Mega Man series, Mega Man 9 (2008), could get in due to fan demand like Sonic did in Brawl
Starfy -protagonist/mascot of the Starfy series, The Legendary Starfy (2009), Starfy was an Assist Trophy in Brawl
Takamaru - protagonist/mascot of Mysterious Murasame Castle (1986, Japan only), appears as a playable character in Samurai Warriors 3 (2009), cameo in Captain Rainbow (2008), Nazo no Murasamejou (Virtual Console, 2008), Sakurai did say that if Takamaru had a new game he would really consider adding him
Tingle - protagonist/mascot of the Tingle series, Ripening Tingle's Balloon Trip of Love (2009), Assist Trophy in Brawl
Toad - major character and mascot of the Mario series, New Super Mario Bros. Wii (2009) through Blue Toad and Yellow Toad, #4 in the Mario category with 27 votes on the Melee poll