I consider Shen my main. Here are some thoughts on making him a bit more "fresh" and fun.
(Passive) Reduce the bonus damage to 8% bonus health but have his auto attacks increase his movement speed by 3%/6%/9%/12%/15% stacking for 2 seconds.
(Q) Convert Q into a skill shot that deals damage/applies the effect to the first minion/champion hit.
Increase damage to Magic damage: 60 / 100 / 150 / 210 / 280 (+ 70% AP) from Magic damage: 60 / 100 / 140 / 180 / 220 (+ 60% AP)
But change the CD to COOLDOWN: 6 / 5.75 / 5.5 / 5.25 / 5 from _COOLDOWN: 6 / 5.5 / 5 / 4.5 / 4.
_
Change heal to Heal: 10 / 16 / 22 / 28 / 34 (+ 1.0% Shen's maximum health) If Vorpal Blade kills the target, Shen heals for 50% of the normal amount instantly. Instant Heal: 5 / 8 / 11 / 14 / 17 (+ 0.33% Shen's maximum health) from _Heal: 6 / 10 / 14 / 18 / 22 (+ 1.5% Shen's maximum health) If Vorpal Blade kills the target, Shen heals for 33% of the normal amount instantly. Instant Heal: 2 / 3 / 5 / 6 / 7 (+ 0.5% Shen's maximum health)
_
(W) Make his W allow Shen to** ignore unit collision **for it's duration. This would give Shen the Molbility he lacks in lane. Also an animation update to better show this would be nice.
(E) Have hitting Marked targets with E reduce the CD of E by 1/2/3/4/5 while it's still in effect, but increase the cooldown of his E to 17/16/15/14/13 from 16/14/12/10/8.
(R) If the target dies before you finish the channel Reduce the CD by 1/2.
Change base stats to make up for any balance issues...bam instantly more fun to play.