Konami probably wasn't interested at the time, given Nintendo's lackluster performance with the Wii U and their overall growing apathy towards AAA game development. Not to mention, the new upcoming game was Metal Gear Solid V, which stars Big Boss, not Solid Snake, and had a much darker tone than, say, Twin Snakes. I used to joke that if (Venom) Snake was in Smash 4, his Final Smash would be him waterboarding the opponent. When Brawl came out, MGS4 was the upcoming game, starring Solid, so I imagine for Smash 4, some execs at Konami might've been like "But Solid Snake isn't in the new game, so there's no point." Also, Snake being in Brawl had more to do with Kojima than Konami, as apparently the story goes that Kojima's son was a big fan of Super Smash and wanted Snake to be in Melee, and Kojima is friends with Sakurai, but the game was too far along in development to add him, so he was put into Brawl instead. And we all know how Konami and Kojima feel about each other, then and now.
Sakurai probably could've gotten Snake back for Smash 4 if he really wanted to, but he would've known about the atmosphere at Konami, and realized it wasn't worth the drama. He got Mega Man, so dropping Snake wouldn't be as big of a blow.
But times have changed. Whereas Snake in Brawl was one of two third party characters, Smash 4 had Mega Man, Pac Man, Ryu, Cloud, and Bayonetta by the end of its life cycle, so third party characters are much more common and span multiple studios, which in turn gets each individual character more attention. MGSV has come and gone, and Konami, despite their apathy towards AAA game development, seems to at least enjoy licensing out their characters for random purposes. From having all kinds of characters have playable cameos in Super Bomber Man R to
getting David Hayter and Paul Eiding reprise their roles for a Ford Focus commercial, they're not being completely idle with their intellectual property.
I also imagine that Sakurai and Nintendo lobbied much harder to get Snake back this time around, given the "EVERYONE IS BACK" goal. Sakurai even said that it wasn't necessarily easy to get every character to return, and that he had to
"twist some arms to make this dream a reality." So it just seemed like the right amount of motivation and timing for this to occur, which is why Sakurai went for this plan instead of cutting the roster down and redesigning the game. Otherwise, it's unlikely that Snake would ever come back.