My local supermarket has cheap frozen coriander/cilantro.
But when I defrost it by leaving it in a bowl for an hour, it turns into a slimy mess.
How can I defrost it so that I get nice fresh leaves?
Frozen supermarket coriander/cilantro is perfectly good to use whilst cooking. Very similar to adding stems for flavour. You'll never get fresh looking leaves to finish the dish from the ice blocks, but stir it in and you will get that background flavour. Delicate leaves, Basil is similar, are either fresh or they aren't.
Don't worry too much about the look and you'll be fine. Bear in mind that you're adding water to the recipe, and put a pot plant on your windowsill for the finishing touches.
In most cases, if frozen food has unsatisfactory texture after thawing, the damage has either already been done while freezing (which might depend on the freezing process used - shock frosting vs normal slow freezing, blanching vs no blanching...), or has happened when the product thawed (eg due to bad cooling chain management on the vendor's side, or an auto-defrosting freezer, or due to the product getting to warm when transporting it from the grocer) and slowly refroze.
What you bought was probably a bag of frozen slimy mess already while in the grocer's freezer. The brand might be cheap because they use less than optimal freezing technique.