Snake's not coming back. Not sure what Sakurai will do with his unused playstyle, but knowing him he'll probably rework another character to fit that mold..
Personally, I would want Pico to take Snake's moveset, but that would never ever happen. I can't really think of any other Nintendo characters that could aside from your example of Wolf taking some of Snake's specials.
The main reason why I think Snake's future is iffy is how uninterested Kojima sounded when asked about Snake's inclusion in Brawl, he pretty much gave an answer where he said the only reason he wanted him in was because he wanted his son to be able to play a game with a character created by him.
As for Sonic, I am inclined to believe Sega would want Sonic back due to what you said, free advertising. However, if Sakurai shows no initiative, and Sega forgets/doesn't care about Smash 4, then I could see Sonic missing the boat this time as well.
You're also right on Mega Man. I think if Capcom USA had any say, Mega Man would definitely already be confirmed for Smash 4. Considering the Japanese demand for Mega Man is strong as well, I am inclined to think that Capcom Japan has followed through on Capcom USA's request for them to talk to Sakurai.
Namco character is tricky. You're right it would be another "Snake situation" where the character is basically forced upon the Smash Bros. fanbase. While is strong demand for a Tales character in Japan, there is no stand out character for the series (its like FE but worse), and no one can really agree on who it should be (at least in Japan). Pac-Man is kind of boring as a prospective addition, though far more iconic and appropriate that most other Namco additions. I think if a Namco character were to happen, we will see it at E3 2013.
I really don't get Sakurai's answer about "third-party characters are difficult to work in due to making sure they don't clash with the rest of Nintendo's characters". Characters like Mega Man and Sonic (and I guess Pac-Man as well) don't clash with most of the cast for Smash Bros. and are basically similar to most Nintendo characters in feel. I think that statement applied to Snake more than anything else.