I recently tried it on Rek'sai, and I must say that it's very good on her. It forces you into a hit and run playstile, since the keystone resets by staying out of combat, but it let's you deliver your combo really really fast. I can't say if Hail of blades is the best choice for rek'sai, but I'll prob use it a lot on her.
That said, Hail of blades has more to do with mechanics tied to any particular champion, rather than normal AA builds. I mean, if a champion just wants to basic attack a lot, then Lethal tempo is definitely the best choice. But if a champion has some mechanic that works with 3 attacks, then Hail of blades can be very effective.
Also, keep in mind that Lethal Tempo kicks in after 1.5 seconds of combat, and is more effective the more you manage to basic attack, something that not all champions can afford. Hail of blades works as soon as you basic attack, and after 3 AAs it has done its job and you can either use some ability or just run away, which very often would be the most sensible choice even when using another keystone.
Lastly, 2 of the other domination keystones have pretty long CDs, and dark harvest works best in the late game, and has a split push element that not many champion really want. Hail of blades has a pretty short CD (despite working only when out of combat), and it helps those champions who want to go in for small skirmishes.
On Quinn, it helps her capitalize on her passive and the W AS boost, all in the span of a few seconds.
On Draven, when you have to spinning axes ready and your Q is ready as well, you can deliver a serious 3 hit, Q enhanced attacks, that are very very painful.
On Vayne it helps deliver your W pretty fast, although after that you pretty off just running away rather than going for a kill, unless the enemy is low health.
Now that I tried it some more, I'd also include Xin and Riven. On the Xin, like rek'sai, it helps him deliver the stun that much quicker; on Riven, it helps her to deliver her combo much quicker (though I'm not a fan on riven, so others can better explain about her).
It's also probably a good option on Rengar, though I personally prefer dark harvest and predator on him.
Last but not least, try it on Morde, for that sweet 3 hit attack combo. It's sexy :D