Shen IS OP compared to the other champions in his class. No other tank has an attack speed, hybrid damage slowing steroid that also gives them a shield on an extremely low cooldown.
While i know Shen is supposed to be a basic attack counter, my problem with him is that - as a player that cant play mages at all - he is just too reliable, even agaisnt spell casters. Illaoi? No problem, just rush sunfire and you outdamage her unless she ults, in which case you press W and walk away until your taunt his up. Garen? Click W. Click E. Click Q. Repeat. I could go on, but i think you get the idea.
Just in case you dont: Shen's Q packs the punch of half an ultimate ability. Its so strong that unless you play a champion with EXTREME sustain (Swain), he can easily force you to use your ultimate EVERY SINGLE TIME its up. And if its not up, his extremely high base stats easily zone you as he can outduel you without even using all 3 of his abilities.
A predictable kit is a poor excuse. Garen, Darius and Yasuo all have extremely predictable kits - yet you'll frequently see them both get picked and win all the way up to Diamond rank.
You keep repeating the same keyword i used in my post - damage. His only counterplay is to outstat him. There is very little you can do mechanically because he is guaranteed to either land his Q on you or force your flash at least once every time his taunt is up. And even if he misses his Q, it still does so high damage you are very unlikely to outdamage him without using your ultimate - which he can easily walk away from and wait out.
This in itself isnt the main problem though. Sure, he can go EVEN with you, even if you have your ultimate up. That in itself isnt necessarily a bad thing.
The bad thing, however, is that if he is put even SLIGHTLY ahead, there is nothing you can do against him at all. You cannot outdamage him, but he sure as hell can outdamage you. He will build full tank and still easily force you out of lane unless you sit under your tower.
What does this mean?
Well, let me make an example. If Darius or Riven gets an early gank and pick up a kill, They get a little ahead. They will likely be bullying their opponent, but they are not strong enough to decisively kill them and, before they get their ultimates, the chance for a comeback is there for their opponent.
With Shen on the other hand? ONE gank is enough. You dont even need a kill. Gank Shen, force his opponent to back off from a cannon minion and a couple regular minions and that's it. That's all it took. Shen is now 10 cs ahead, he can pick up a 800 gold item while his opponent has a 400 gold item and Shen is now zoning his opponent. He can easily soak up anything they throw at him, and he is free to dash at them ANY time they attempt to go for minions because they are not going to be able to breach his defensive items.
He snowballs even worse than champions like Zed, Darius, Riven or Draven.
If you are a Shen main, you have probably faced Vladimir before. You'd think Vlad would be a decent shen counter - long range, low cooldowns, many health items and high sustain.
Nope. Shen destroys Vladimir. Vladimir either pools away from Shen's taunt or lets himself get hit and chunked for 60% of his HP in 3 basic attacks from Shen. This of course assuming they have both reached level 3 without any ganks.
Shen is a TANK. He shouldnt be allowed to build full tank and deal Warwick-tier damage. Speaking of which - he's a warwick counter! Warwick is seeing a stable ban rate (at least in platinum, where he seems to get banned every single game) and is considered one of the strongest junglers in the game.
And yet Shen counters him. One bramble vest and Shen easily 1v1's Warwick. A champion that almost no other champions in the entire game can 1v1. And Shen is still only building defensive tank items.
Shen is almost at tank Ekko level of counterplay. He is less mobile, so if the enemy team gangs up on him (aka 4v1, like a juggernaut) then he might die.
In other words, Shen, a TANK with a NON-COMBAT ULTIMATE is such a high threat he requires juggernaut-level attention to control. He will easily burst down marksmen, mages - anything that doesnt stack a lot of health or heal a lot constantly.
All while still exclusively building defensive items.
Now about the matchups you stated - have you ever seen a Rumble vs Shen lane? Yes, Rumble can bully Shen SLIGHTLY early game (Shen's passive shield will deflect the majority of Rumble's damage unless he all-ins, and Rumble is forced to push the lane to bully Shen)
Now if Rumble does bully Shen, and Shen gets a gank and picks up JUST ONE KILL on Rumble, Rumble is suddenly no longer capable of even contending the lane. Shen will easily outdamage him HEAVILY, and can also zone him from minions by physically blocking his harpoons and Taunt-engaging every single time Rumble attempts to farm with his flamethrower.
Gangplank uses Q on Shen. Shen presses Q. Shen loses no health. Gangplank loses mana and gains minion aggro.
Gangplank basic attacks Shen with a true damage-empowered basic attack. Shen loses 5% of his health.
Shen basic attacks Gangplank ONCE with a regular Q-empowered basic attack. Gangplank loses 15 to 20% of his health, depending on his rune page.
Cassiopeia vs Shen. See Rumble above: Cassiopeia will bully Shen at the very start of the game, and then she runs out of mana. Shen farms.
Cassiopeia buys mana items. Shen buys magic resist. Shen dives on cassiopeia when she attempts to bully him. Shen easily deals 40 to 70% of Cassiopeia's health in one combo. Shen might lose up to 40% of his health from this trade, which he quickly regenerates due to high base health regen. Cassiopeia has no regen and is now zoned by Shen who can easily kill her should he land a taunt, so she will stay at low health until she recalls to base.
Swain vs Shen is the only matchup Shen cant deal with. Swain's ultimate is unblockable and the healing he recieves is not reduced by Shen's magic resist, hence Shen has no way of winning this matchup. Still doesnt help me, as i do not play mages. But that's ONE counterpick.
Darius vs Shen. Pass. Darius beats Shen easily without jungler assistance, and even if Shen is put ahead Darius will allways be a threat - as well as being able to survive lane trades, due to his innate sustain and crowd control.
Trundle vs Shen. Trundle attempts to poke Shen early game. Trundle bites Shen. Shen clicks Q, blocks the entirety of the bite damage and, despite having his AD lowered, deals roughly 20 to 40% of Trundle's health in three basic attacks while he loses roughly 20% from Trundle's Q-empowered basic attacks.
Shen buys bami's cinder and ninja tabi. Trundle can no longer actually damage Shen, while Shen easily chunks Trundle every single time his Q is up - even more if he pulls it through Trundle.
Trundle gets ult. Shen stops engaging with his E and simply trades with Trundle through his Q and his W. Shen is still constantly poking Trundle and controlling the minion waves.
Trundle uses his ult on Shen. Shen activates his W and begins to back off. Trundle uses his ice pillar to block off Shen's taunt dash. Shen pulls his sword through trundle as he chases, empowering his basic attacks. Even with Trundle's ult applied to him, Shen is still being shielded by his passive for a large chunk of Trundle's basic attacks - Trundle has stolen Shen's armor, which does not protect at all against Shen's empowered Q basic attacks. Trundle loses a lot of health, mana and cs from trying to fight Shen for lane dominance. Shen loses a little health, which will quickly refill from high base health regen. Once his cooldowns are up, he is free to go back to bullying Trundle who is now low on mana.
I'll add a couple of my own here:
Garen vs Shen. Garen attempts to use Q on Shen. Shen parries it with his W. Garen uses his E-spin on Shen. Shen taunts through Garen away from him, pulling his blade through Garen. Shen turns and basic attacks Garen. Shen loses 10% of his health, his passive blocking most of Garen's spin. Garen loses 20 to 40% of his health to Shen's taunt and Q, and is forced to back off while waiting for his cooldowns.
While Garen does have innate bonus magic resist, Shen both has a high frequency shield and high health regen, which is on par with Garen's passive health regen until Garen either gains a lot of bonus health or his passive is upgraded by level increase, at which point the laning phase is likely already over.
Shyvana vs Shen. Shyvana can contest Shen for lane dominance due to her own hybrid damage and passive. However, she can only stand toe to toe with him - even with her ultimate, she will still only go even with Shen through skill - which means one jungler gank or one roaming mid laner and she loses the lane.
On the other hand, if her jungler grabs an early drake Shyvana can win this lane without actually recieving any direct jungler help of her own. With her passive upgraded, she will likely be able to outdamage Shen in a 1v1. Still, this is provided it has been a 1v1 the entire game.
Taric vs Shen. Believe it or not, Taric can actually outdamage Shen. However, he has extremely steep mana costs and a weak early game, so he will likely be behind Shen in cs by the time he gets enough items to go toe to toe. Also, if Shen recieves a gank this lane is over.
However, Taric's sustain is superior to Shen's. Not only does Taric constantly heal himself, he also deals hybrid damage on every single basic attack, has innate armor from his W and can shield himself about as often as Shen can.
If Taric can rush a mana+armor item such as glacial shroud and then go straight for either adaptive helm, abyssal mask or spirit visage, he will be able to push Shen out of lane.
But once again, this depends on the jungler. If Shen has a heavy physical damage jungler (which he often will, given his hybrid nature) Taric will be unable to build a lot of magic resist and thus be unable to actually win the lane.
I'm actually running out of space. I'll elaborate if you care for more matchups, but at this point i hope i've proven my knowledge of these matchups. Shen has no reliable counters.