So I just had a stupid idea:
Change her passive to something else (more on this later). Casting Shunpo on a target marked with Bouncing Blades resets the cooldown of Shunpo and Sinister Steel, and takes 2 seconds off her Q cooldown. Her ult is no longer a channeled DoT. Instead, after a short cast time, she fires an AoE outwards, similar to Vladmir E, where every target hit is marked with Bouncing Blades, dealt some damage (a lot less than the current full channeled ult), and slowed. I'd also take the damage she loses from her ult and load some of that into her W. Some balance levers include her Bouncing Blades priority (ie minions/monsters vs. champions) and the number of bounces, the slow on her ult, and simply to changing damage numbers. As for her passive, I think it should also be some sort of utility, like maybe increased movespeed towards marked targets, or something.
The idea here is that she has greater mobility inside a fight, provided she gets her Q off, but she has periods of vulnerability when casting her Q, and her mobility is also more limited based on who is marked by Q or R, and because her W consumes the mark as well, she has to be more careful of how she uses her W so she still retains her mobility. I believe Riot has said that champions are easier to balance if they have utility instead of just pure damage (which is one of the reasons for new Ryze ult vs. old Ryze ult), so I think making Katarina less reliant on just sitting in a team and channeling her ult (which she barely does anyways) and giving her more utility around how she ults and keeping track of her Bouncing Blade marks will make her more interesting, and also give players more windows for counterplay (everytime she uses her Q or runs out of marks), instead of just waiting until she channels her ult and trying to disrupt it before she kills someone and gets the reset.
The obvious downside is that she's Yasuo 2.0 (0.5?), where she gets a ton of mobility, but I think having it gated by her marks makes it more manageable than Yasuo. It also raises interesting decisions for Katarina, like how she manages her marks to maximize damage with Sinister Steel while still leaving her places to get Shunpo resets. One final change is to change the VFX on her ult (obviously, since it's a completely different spell). I'm thinking a lotus appears under her and the leaves fire out, marking the enemies.