There have been studies on this, both with paired clicks and long streams of clicks. Normal listeners can detect changes of the sort you describe with essentially perfect reliability down to about 45 ms and with better chance performance below 30 ms. I haven't been able to find a study measuring the minimal threshold for this change, but from the studies I have found it should probably be in the 10-20 ms range.
As for how the interval affects it, the answer depends on the direction of change and the direction of interval change, so it is hard to give a single answer. The affect seems to be larger at larger interval changes.
Note that this is a very low-level task, with slightly higher modulation rates processed at the very lowest levels of the auditory pathway. It is also a task that is highly "conserved" evolutionarily, that is it is very consistent across species. Fish have similar performance to humans at this task. And not that in the stream study, it used mismatch negativity, which is a change in electrical activity in your brain that occurs even if you are not paying attention to the stimulus and don't consciously notice the change.