As a Katarina player I can give a few things that I KNOW tick me off early game as far as melee people go.
Most melee characters have a ranged skill they can use that chips off a decent chunk of HP, those really can force Katarina back early game, she is a lovely harasser but you have to play the player, scare a katarina player early on with a death or near death and they will GENERALLY be much more timid. This doesn't mean charge into melee range through teams of enemy minions, get focused, and then watch as Kat laughingly finishes you off, this means do hit and runs with CC abilities and the like. Kat HATES slows, stuns, and silences as they neuter her early game from doing just about anything. You don't have to kill her, just make her worried that "one more of those attacks and some basic melee hits and I'm out!"
Time your strikes to creep waves, make her retreat when a wave is coming so she misses out on one or two minion deaths EXP wise, this can make a level gap appear faster than you might think, and getting your ultimate before your opponent can really turn the match. All of a sudden there's that one important enemy death that puts them behind and you in the lead for then, if kat is dead or back trying to regen/heal she cannot build up to a killshot.
Keeping her from the EXP and gold keeps her from gaining the crucial attack to HP ratio against your team and can render her meek endgame and easy prey. Nothing is as frustrating as being Katarina, never dying, but being utterly unable to kill an enemy Champion because you have a bad gap in levels and gear because playing conservatively kept you behind.
On the other side, too aggressive of a katarina will lead to a LOT of deaths and gold for your side.
I know that farming can be vital, but you have to time the farming to when you can force her back, get a feel for the timing of when she can and cannot bouncing blade, and if she shunpos don't be afraid to wail on her a bit with melee basic attacks, just don't chase too far. Early game especially one or two melee basic attacks does as much as a shunpo, and depending on the hero can do more than shunpo can.
Make her scared or make her die, hold back on the farming if the timing is bad...gold can come later, just try to keep her from getting too much either.