First thing's first, Garen's passive heals for jack shit before level 11. His early game is his weakest point, so if you don't properly abuse him that's kind of on you. Maintain the wave in a safe spot and zone him from farm, his W has a long cooldown and is a huge portion of his defense before he gets items, so the longer you keep him from tanking up the further you can set him behind.
Garen has his E and his Q, and right now Q max is the most popular. The only thing you need to fear from his spin is it's built in armor shread, which effects you after you get hit by it four times. If you're playing a champion with some sort of defensive ability try to time it with his Q, that's most of his early damage. Once Garen's Q and E are on cooldown he has nothing but some rather weak auto attacks, so time your stuff properly and you have a few clear windows to fight him.
As for how his "R wins him every melee trade" you're just being silly. Trades are smaller fights designed to get your opponent low. A full scale fight, on the other hand, can either be avoided or won by playing around Garen's cooldowns. Kled in particular can just run away if Garen tries to all in while ahead, and he can very easily stand and fight otherwise. Just play around that W so you don't waste a bunch of your damage.
TLDR:
- Zone him from farm while he is weak.
- Don't throw your damage at his W.
- Pick your fights and play around cooldowns.
If this isn't enough for you then you either need more practice with your champion, or should just go super cheese and get an early Hexdrinker. The Hexdrinker shield completely eats Garen's level 1 ultimate.