How are melee based champions being shut down by Randuin's Omen? They still deliver 80% of their DPS. They still have 3 multiplicative stats (AD, attack speed, critical chance) that have very high caps. They still have item choices they can make to puncture any amount of armor.

buff blade of the ruined king and add an item that gives atk speed, movement speed and slow reduction for melee champions? Both seem like good ideas to me.

Attack Speed Slows are just another defensive multiplier like Health and Armor. If someone gets 20% damage reduction or 20% more health it accomplishes exactly the same thing as a 20% attack speed slow does - increasing their EHP indiscriminately of whatever attributes you utilize to bolster your auto attack DPS. As such you just build more Attack damage, attack speed, critical strike chance, armor penetration, or cooldown reduction to make up that DPS loss. Itemization in LoL is there to allow you to build super-tanky, glass-cannon, or somewhere in-between. If someone builds full-tank they're going to scale to a point it takes longer to kill them then it did at level 1, if you build full damage you're going to kill anything that didn't counter all that damage with an equal amount of defenses faster than a level 1 fight would otherwise end. When dealing DPS it's pretty important to choose targets you can survive long enough to kill and avoid targets you can't. When playing a tanky champion it's important to know what fights you can pick your team can win and avoid picking fights your team will loose. Randuin's Omen doesn't do anything unusual in that sense regardless of what champion you play.

So yes, you can counter attack speed slows. In exactly the same way you counter health and armor. With more damage.