Is there way to add the same block to cache in different versions to cache, for example for different sorting in products' grid, but for the same request params - for example random sorting, which should be different every time? It would be good to have for example 10-20 versions of block with different order of products and just take different versions from cache. It is not good solution to clean cache for every request with random sorting parameter.
This is assuming that shuffling the shown results (limited to the items on page 1) is sufficient.
If you want to shuffle more products, spanning multiple result pages, that would be more difficult are require server side customization.