IIRC Wasn't Kha released near the time BC could stack, and that's why everybody called OP? The problem right now is that he is useless in teamfights because of his isolation damage being lost. Unlike Zed or LB, he also only has one way of going in, and unless he picks up a kill, he almost always dies, unless he isn't focused and can E out. And that is perfect in his design. The other example of this type of assasin is Talon. BUT, simply because he can effectively mid lane, he outclasses Kha. Kha can only be picked in jungle , but new jungle is a lot more accustomed to tanks now, with Gromp and Cinderhulk.
The things that need work are his W, R and passive.
The evolution system should just be stuck into his passive, and his R should be buffed. 80 second CD + 100 mana for 1 x2 second stealth that only grants MS and no collision between units is pretty pathetic. Only upside is his passive comes back up. I see it being somewhat better when he evolves it, but adding an extra 4 seconds doesn't add a new aspect to his ability
To buff R: Make it so when you ult, isolation is negated and you do full damage on Q for 6 seconds. Now he can use his ult for something else rather than escaping/chasing. Using his ult in teamfights is actually meaningful, because now it's more of an all in tool, you miss your chance, you don't do your job as an assassin. Reduce CD on his ult to 70 seconds all ranks, and 100/90/80 mana cost. When evolved, how about creating an illusion of himself for 1 second running towards a random direction? Kind of like LB's passive. But, the number of times he can stealth doesn't increase, only duration.
To buff W: Make it go through units, simple. If he hits a unit and is near it, he still get's healed. This way, you can move him out of jungle, and into mid, a more suitable place for assassins. Change it from 100% Bonus AD Scaling to 0.7 AD, and remove 20% monster damage.
To buff Passive: Well let's see. For one, the scaling should be removed, because there is no item involved with AP that Kha buys, and if you say Trinity, you are probably the same guy who buys IE on Talon and Zed. Instead, let his passive reset on stealth plus Isolated Q's, but it only applies 50% damage and no slow if used on the same target within 4 seconds. So, it means if you get caught out, you die a lot quicker, instead of having it drag out into a chase, which should be the case with assassins. Also, he can use his passive in mid lane without having to go in bush or out of vision, Let it still deal magic damage, but add bonus AD scaling maybe?
He needs to be turned into a laner. Jungle right now belongs to tanks, and there is no way to make a balance between the two without making one useless, because it will always be the decision of picking one over the other.