They clearly thought Greninja was much, MUCH stronger than he was. I wouldn't be surprised if they considered him the best character in the game before 1.0.4 and would be shocked if they considered him any worse than top 3. I suppose his strong results in Japan didn't help but he was hardly dominant... I don't think his results were any better than other top characters at the time.
Wasn't Greninja mostly used in Japan during the release of the 3DS? Diddy wasn't used as much and how vectoring worked could have made Greninja much stronger than he seemed like how Luigi and Mario were much weaker characters because of how vectoring worked during release.
Rosalina had results since day one and yet, somehow it never seemed to be considered that maybe a character like her being able to kill at sub 100% is okay. Rosalina is not a heavyweight who killing at sub 100% is okay; she's a lightweight with a unique play style because of Luma and disjoints on pretty much her entire moveset. Rosalina is mobile in the air and on the ground, her landing lag can be nullified by Lunar Landing, and her jab kills fairly well. And despite all of this, she gets somewhat minor nerfs.
He really was trashed. I just found out all of his smashes had their range nerfed in that patch, and Fair may have done as well, on top of all the other crap that happened. Honestly I think he was lucky to end up mid tier/bottom of high tier, the huge nerfs across the board could easily have landed him in low tier. You don't nerf EVERYTHING strong about a character at once, it just baffles me that they thought that was good balancing no matter how strong they considered him. Especially considering how young the game was! Eugh.
Justifiably, Greninja wasn't intended to be that strong and more of an ambush character who plays strong mindgames and punishes well. If he was much stronger, then it might not be a bit fair when another punisher, Ganondorf, would look pathetic. Some things like Shadow Sneak's techniques being removed already was kind of a given since pretty much everyone's techs were removed - I wouldn't be surprised if Falco's slide out of Fast Fire Bird was patched out if it was more common.
What's not justifiable is Meta Knight's. People complained about Brawl Meta Knight and now that isn't broken, people are complaining about Meta Knight not being Brawl Meta Knight? Seriously? When people are iffy about whether or not Meta Knight is bad or good, it's because he's being compared to a freaking SNK Boss from Brawl. Meta Knight is at the very least, a mid tier. There is nothing about Meta Knight that should put him lower. He has shield issues, he's light, but his attack speed, his ability to juggle you to death, his advantage and disadvantage are good, and so is his neutral. This little knight has one of the best dash grabs, a good dash attack, the fastest Smashes, fastest aerials, and he can pressure you if people let him vulture around you. Mach Tornado covers ledges well along with dealing ludicrous amounts of damage if mashed well - around 30%. Shuttle Loop is an abusable kill move that makes Captain Falcon wish his Falcon Dive could have been used for Uair juggle finishers. This is a strong character held back by a broken past? He's much more of a fairer character after being toned down from Brawl, but people want a broken character? Oh, wait. They want Melee/Brawl Falco and Melee/Brawl Marth with Melee/Brawl Falco being notorious for broken stuff.
As far as SSB4 goes Greninja was nerfed the hardest but I suppose you could say the same about MK from Brawl. He was lucky not to end up total garbage considering the transition from Brawl to SSB4 was pretty tough on him. I guess Falco and Dedede weren't so lucky. They probably knew who the top characters were in Brawl going into SSB4 development but they had a lot of results and community tier lists to work with.
At the same time, as you said, at least he ended up being able to contend for mid tier or low-high/mid-high tier. Greninja still has tools to compete against everyone with what made him strong being toned down, but not butchered. I don't want to complain, since it gets me and everyone nowhere, but whatever... You want butchered? Go look at Falco. What made Falco strong was his ability to break games. Fox and Falco abused the hell out of Melee and Fox being a good character since 64 didn't help as he was even better in Melee. Brawl showed a Fox where pure design lets him stand tall and proud and if Brawl didn't have random tripping, chaingrabs, and multi-hits worked better, then Fox would have done much better... Oh wait, isn't that what Fox is doing in Smash 4?
Falco was given one of the most if not the broken projectile of SSB and then they decide to make it even more broken in Brawl. Tripping meant nothing to Falco since he could just hop about walling you out with lasers, chaingrabs might as well be his name, and multi-hits? Why use those when you have a powerful, fast meteor and the ability to rapid-fire lasers that cover the entire stage that stun and rack up a ton of damage? Man, you could have removed all of Falco's moves, but his grab, Specials, Bair, and Dair and he could potentially have been a mid-tier with only 7 moves. An exaggeration, but that was how broken this bird was in Brawl. Hell, the reason he probably even stayed up that high was his Blaster.
So, how do we "balance" Falco from Brawl? Let's remove auto-cancel from Blaster and ignore the end lag, make his grab slower than Ganondorf's and slow for a melee fighter, ignore increasing his horizontal movement speed in a significant way - 1.432 to 1.472 - while increasing Fox's air speed which Falco shared in Brawl, double the startup on Dash Attack - not that abusable of a move - and Fair - a frame 6 frame would be abusable, but it wouldn't mean instant death if you can't land this move with major landing lag -, increase Nair's landing lag by 6 - it was 9 in Brawl -, increase his Dair startup by 11 frames without taking into account how he's going to be able to land that when his old Dair was kind of difficult to land without a setup as most moves are, make Bair look like Wolf's in animation, but not accounting for why Falco needed a sex kick or why Wolf was able to abuse his Bair which was actually slower than Falco's by 2 frames, and oh, let's add one more frame to Side Smash's startup because why the hell not? What got "buffed"? Fall speed to match Brawl Wolf's fall speed. Debatable as it could factor into Falco being easier to juggle now. I'm not sure about knockback changes, but end lag, landing lag, the rest of his moves startup, and damage changes aside from throws, Reflector, and Fair are pretty much the same.
What made Falco strong in not a broken way and from a design point was his ability to zone or anti-zone. If Falco could something similar to Mario and Luigi - covering their approaches or force approaches -, he wouldn't be in this situation of having a projectile only really useful for off-stage and tacking on damage he physically cannot reach because his poor mobility. What made it too strong was the ability to auto-cancel his Blaster made even more broken in Brawl when he could fire SHDL instead of being limited to SHL. Luigi can't auto-cancel his Fireball, but people knows how strong his Fireball is to his game. His weaknesses from previous games still exist: poor recovery - in Smash 4, it's the stupid hitbox on Falco Phantasm making it worse and that pretty much everyone's recovery is good in Smash 4 -, poor ability to confirm kills - he can rack up damage and kill well, but he can't confirm them easily made worse by having a slower spike and the end lag on Blaster preventing him from stalling his opponent for a kill -, and a poor disadvantage - fast fall speed and slow air speed - made worst by losing his old Bair with a front hitbox.
Marth on the other hand, was toned down too far and given such a difficult playstyle. If Marth was in a Street Fighter-esque game, then spacing his tippers would be much easier and much more rewarding than trying to space tippers in a game where a monkey can run and flip around everywhere or a blue hedgehog can zip by making you look stupid. Marth at least his extremely powerful punishes, the subtle buffs to his Dancing Blade and jab make his game less painful, and customs, especially Crescent Slash, adds a kill confirm from grab. Having natural disjoints, Falchion, and being very mobile help as well.
and 
