I think it's funny how your info is right, but your grasp of the info is not.
Any champ with the right runes and masteries have a better winrate than champs with no runes and masteries.
So what you are saying is that because of his lifesteal and crit, he is unkillable. By that logic, ADCs are the best class in the game and can survive better than a fed Poppy.
He dominates the early game in the same way Irelia can. By using the mechanics given to her, she is able to dominate the early game with early trades that usually result in a first blood or a back on their part. Yasuo does it in a different way than she does, but with proper knowledge of the game and your strengths and weaknesses as well as his, you can easily beat him.
The reason he does not fall of midlane is probably because he got fed early, which you need to prevent through the help of your jg. If he does not fall off at Mid game, which he normally does if he has not gotten many kills, it was your team's fault. At a normal pace, Yasuo will not have enough tools for surviving a teamfight. If he gets a few kills early and is beginning to ramp up, DEAL WITH HIM NOW. This is the ONLY time when you will be able to deal with him if he already has a few kills. If you don't he WILL snowball, just like most of the champs in this game.
His late game is supposed to be strong. Some champs, like Shaco, lose their usefulness unless super fed. Yasuo's job is to get early kills, survive through mid game, and use what he has to ramp up to late game. If he had no damage at late game, then he would have to be a frontline tank with mobility and CC, which NO ONE would like. Instead, he is a relatively squishy fighter that relies on his crits and lifesteal as well as proper management of his skills to teamfight. If he is not careful, he ends up killing himself if he gets focused. A GA is useless if his team won't assist him.
Also, the nerf you proposed is not needed at all. He needs nerfs, but not there and definitely not in that way.
He needs to be changed in a certain way. Give him a reason to max his Q. He has literally no reason to right now.
Give him two build paths to go along with maxing Q or E.
If he maxes E, he builds a more squishy, mobility based build. He sacrifices tankiness and sustained dmg for mobility and burst. Something like 
. He would act closer to an assassin than as fighter as he is now.
If he maxes Q, he sacrifices mobility and burst for tankiness and sustained dmg. This would still let him have a bit of mobility, but not as much so. His main priority would be armor shred with his ult and sustained dmg with his Q and Autos. Something like 
is broken because he gets so much out of 
.