Yep, I see it too. Except I think there's one other thing that needs to be factored in, and that's ranged abilities. All the new champs have them, even the ones that are supposedly "melee."
Mobility Creep is real, but with the right boots/runes, even immobile champs can become reasonably mobile (I was running Mobi boots on supports in season 3 before it was something you saw in literally every support build.)
But when champs can shut you down from far away, it eliminates the need for them to take risks. This is particularly unforgivable when they're supposed to be a melee champion like Rek'Sai or Mega-Gnar. The whole point of melee champions is that they're supposed to shut you down if they can get close enough. That's the built-in risk of a melee champ and why they are usually tanks. In a smaller champion pool, this is why the more immobile champs have limited CC of their own, so they get rewarded for hitting you with it. Now suddenly we can't release a melee champ without them being really mobile...and also able to poke you when they aren't in your face, and as the OP stated, usually with CC as a random bonus too.
I would argue that the biggest issue is not just that all the new champs have mobility and CC, but that they ALSO have at least one ranged poke ability too (which often is their CC.) As a result it's not just the immobile champs that get crowded out, it's the strictly melee ones as well. It's as if Riot systematically decided all champions need to be very mobile, have some form of CC for counter play (or making plays) and also have poke, or they're simply not viable. I just call that lazy uncreative design. Or "League of Dodgeball."
Let's go through your list and add range to the equation:
(Hella mobile, oh and has that stupid burrowed Q which is a long range AP poke that's designed to find people in bushes or hit them over walls which she doesn't need cause when she's burrowed her passive sees them anyway.) Rek'Sai has already had her melee damage nerfed twice because it was way too high, and her tunnels/ult give her the mobility she needs to stay viable as a melee, but she gets this long range poke too? She seriously doesn't even need it. It literally feels like an extra feature you might remember you have.
(Marksman, like I even need to say anything else, but I will, her Q gets even more range if it kills something. I'm not sure what the range is on her rend, but it could probably be shorter.)
(Can literally drink a mojito in Bermuda while his sand soldiers wreck your face, oh and if that's not enough, have a turret. Now Azir can literally hit you no matter where he is.)
(Now this one is really ridiculous. I had the thought the other day, if Gnar was ALWAYS Mega-Gnar, would he still get used as much? I'm guessing probably not. He's so slow in Mega-Gnar that his tankiness is forgivable, but considering his only real attack in mini-Gnar is super long range, and the fact that he can still throw a projectile that slows you in Mega-Gnar is just stupid. If he was ALWAYS Mega-Gnar, maybe that would be necessary cause he is slower in that form and can't hop, but the fact that he's a long range threat half the time means he doesn't need to be the other half too. Besides Mega-Gnar's ult is all the CC he needs to make game changing plays.)
(Not only does he have mobility and range, but all of his offensive abilities are forms of CC. Still he's picked for his defense and mobility, not his offense. And his mobility is pretty much limited to where his allies are, so I wouldn't say he's the worst offender here.)
(Moonraker, Diamonds Are Forever, Goldeneye (Good name for Arclight Vel'Koz btw,) and Die Another Day were all about James Bond trying to save us from Vel'Koz destroying the planet from orbit. At least he's relatively immobile, which is why he's not contested.)
(Every third attack, Yasuo ults you from the random ranged CC ability that's in his kit. Or you know, someone on his team knocks you up instead, and Yasuo ults you. Although he's so mobile the range on his hurricane isn't the problem.)
As you can see with Vel'Koz being the prime example JUST range doesn't put a champion instantly into the pick/ban tier, but having range and mobility both, makes them instantly broken, I mean, how many times did they nerf the mobility+ranged God Lucian before people finally stopped picking him in every game? Like 4? Same thing with Yasuo. Lucian is #9 on this list btw, Jinx was #8, her range is sick too, she has 2 different types of cc (chompers and zap) and her passive makes her mobile as hell. She's actually getting a little bit of play in pro games currently, and I'm not the least bit surprised.
By itself mobility is ok, by itself CC is ok, by itself range is ok, two of these things together is what makes a champ dangerous and if a champion can easily or repeatedly do all three...you'd be an idiot not to pick/ban that champ in 100% of games, and pro players aren't idiots, so they pick/ban these champs in 100% of games and it gets really boring.
What seems to be the problem though is that this honestly does invalidate like 75% of the older champions, and then when they get reworked, they get reworked into having all three of these abilities, which makes the game stale because there's no more variety. "Everyone can do everything!" instantly devolves into "So why ever pick the ones who don't do it best?" At least right now we have some (non-competitively viable) champions who are still very threatening and fun to play without all three of these things in their kit when they get rolling. Champs like Poppy, Singed, Veigar, Volibear, or even Cassiopeia (who is getting picked in Chinese games currently [(they're still on 5.1 though.)]