Randomized Algorithm with random input
As you said, it is enough to point out a distribution (this could be any distribution) on which every deterministic algorithm fails. Now, if there is already a distribution given, and you can show that any deterministic algorithm fails on this one, then this provides also a lower bound for randomized algorithms. You can use any distribution in order to apply Yao's principle.