Fix the finite sets $\mathcal{X}$ and $\mathcal{Y}$, and probability mass functions $P_X(x)$ and $P_Y(y)$ on these sets. Assume each value of $P_X(x)$ and $P_Y(y)$ is rational.

For each $n$ such that $nP_X(x)$ and $nP_Y(y)$ are integer-valued, let $(X_1,\cdots,X_n)$ be a random sequence with $nP_X(x)$ occurences of each $x \in \mathcal{X}$ (all such sequences being equally likely), and let $(Y_1,\cdots,Y_n)$ be a random sequence with $nP_Y(y)$ occurences of each $y \in \mathcal{Y}$ (all such sequences being equally likely). [NOTE: This distribution can be obtained by applying a random permutation to any such sequence].

Fix a bounded function $f(x,y) : (\mathcal{X} \times \mathcal{Y}) \to \mathbb{R}$, and let $S_n = \sum_{i=1}^n f(X_i,Y_i)$. Does the distribution of $\frac{S_n - \mathbb{E}[S_n]}{\sqrt{\mathrm{Var}[S_n]}}$ tend to $N(0,1)$ as $n \to \infty$? If so, what can be said about the rate of convergence?

It is worth noting that if the $X_i$ and $Y_i$ were i.i.d. on $P_X$ and $P_Y$ then $\frac{S_n - \mathbb{E}[S_n]}{\sqrt{\mathrm{Var}[S_n]}}$ would tend to $N(0,1)$ by the Central Limit Theorem. Furthermore, by the Berry-Esseen Theorem, its distribution function $F_n$ would satisfy $$\Big| F_n(z)-\Phi(z) \Big| = O\big(n^{-\frac{1}{2}}\big)$$ uniformly in $z$, where $\Phi$ is the distribution function of $N(0,1)$.