This is a question in the form of an answer;

A: a patch which loads a soundfile and stores all "zeroes" to a table. Then randomly scans the soundfile from zero to zero.

Q: Is there a tilde object which detects zero-crossings, and can it be used to 'shuffle' samples with no clicking?

http://www.pdpatchrepo.info/hurleur/zero.pd

A: No

Q: Does a segment bounded by two zeros necessarily satisfy "with no clicking"?

These are our enemies with this algorithm...

1. Multiple consecutive zeros

2. A soundfile with a significant DC offset (perhaps a soundfile with no zeros at all !)

Replace "zero" with "local average minima" and the question to your answer is "What could I use [env~], [threshold~], [min] and [max] to accomplish ?"