If I can efficiently uniformly sample both $A$ and $B\subset A$, can I efficiently uniformly sample $A-B$?

As posed in the question; the statement naively seems like it should be self-evident but there are no algorithms that come immediately to mind. Suppose I have some domain $A$ (in my case a subset of $\mathbb{Z}^n$ for some $n$, but I would expect any answer to be independent of that structure), and a domain $B\subset A$. If I have an efficient algorithm for uniformly sampling from $A$, and an efficient algorithm for uniformly sampling from $B$, is there any way of 'combining' these to get an efficient algorithm for uniformly sampling $A-B$? I can certainly rejection-sample, but if $|A-B|\ll|A|$ then there's no guarantee that that will be efficient.

Theorem: For any given $A$, either there are good algorithms to sample every subset of $A$, or what you're describing is impossible.

Proof (perhaps slightly informal): Suppose there are some "problematic" subsets of $A$ (those which cannot be efficiently sampled). Let $C$ be one of those subsets. From the fact that $C$ is problematic, it follows that $|C| \ll |A|$ (otherwise $C$ could be dealt with by rejection-sampling). Now let $B = A \setminus C$. Clearly, rejection-sampling does work on $B$, because $B$ is almost the entirety of $A$. So now we have algorithms for both $A$ and $B$, but no algorithm for $C$. Q.E.D.

Here's a ridiculous example: $A = \{(x_1, x_2, x_3, x_4) \mid x_i \in \mathbb{Z},\; 2 < x_i < 10^{10^{10^{1000}}}\}$ and $B$ contains only those quadruplets of numbers which are not counterexamples to Fermat's Last Theorem (i.e. such that $x_1^{x_4} + x_2^{x_4} \neq x_3^{x_4}$). It's trivially easy to sample $B$, but that gives us no clue whatsoever about how to do $A \setminus B$.

StackExchange Computer Science Q#127867, answer score: 3