One straightforward way to solve problems of this type is to look for solutions in tiny discrete probability spaces.
This post begins by explaining the motivation behind a contingency table construction (which incidentally shows that this has to be one of the simplest possible solutions). After exhibiting appropriate tables, it attends to a technical point (almost always overlooked, perhaps because it's intuitively "obvious") concerning the construction of a single probability space that will support all four random variables simultaneously. Given the care with which the question is stated, it seems that such completeness and rigor might be desirable.
A quick check shows that no solution is possible with Bernoulli (two-valued) variables, so let's move on to variables that can take up to three values, which for simplicity we might take to be $0,1,2$. A pair $(X,Y)$ can be summarized in a contingency table form: a $3\times 3$ table presents the probabilities of each possible outcome $\Pr((X,Y)=(i,j))$ in row $i$ and column $j$ (indexing from $0$ through $2$). Of interest is our flexibility in choosing those probabilities. We need there to be at least two distinct bivariate distributions, $(X,Y)$ and $(X^\prime,Y^\prime)$, that meet all the assumptions of the problem. Let's count constraints.
In addition to requiring that all nine probabilities sum to unity (one linear condition), the problem statement imposes two additional (linear) conditions on the row sums (giving the distribution of $X$), two additional (linear) conditions on the column sums (giving the distribution of $Y$), and four additional (linear) conditions arising from the distribution of $X+Y$ (because it can take on only the five values $0, \ldots, 4$). Although these $1+2+2+4=9$ constraints on nine numbers might suggest a unique solution (namely, they all equal $1/9$, the case where $X$ and $Y$ are independent) it turns out they are redundant. Finding that redundancy is a routine matter of linear algebra: that's the point of using this approach. It can produce examples automatically.
We easily obtain the following form for the general solution. The table must have the form
$$\begin{array}{l|rrr}
&Y=0&Y=1&Y=2\\
\hline
X=0 & \frac{1}{9} & t & \frac{2}{9}-t\\
X=1 & \frac{2}{9}-t & \frac{1}{9} & t \\
X=2 & t & \frac{2}{9}-t & \frac{1}{9}
\end{array}$$
You may easily check that varying $t$ between $0$ and $2/9$ (a) keeps all entries non-negative while (b) preserving all row sum, all column sums, and the sums for constant $X+Y$ (which are sums along upward rising diagonals: $\Pr(X+Y=0)=1/9, \Pr(X+Y=1) = (2/9 - t) + t = 2/9$, etc.).
For future reference, let the value in the $i,j$ entry of this table be called $p(i,j;t)$.
The case $t=1/9$ gives $$\Pr((X^\prime,Y^\prime)=(i,j)) = 1/9 = (1/3)^2 = \Pr(X^\prime=i)\Pr(Y^\prime=j).$$ In this case, $X^\prime$ and $Y^\prime$ are independent. Any other $t\in [0, 2/9]$ gives an example of the non-independent distribution of $(X,Y)$.
This is not quite a complete solution, because we must construct a probability space that supports all four variables simultaneously. With these distributions in mind, we might consider $$\Omega=\{0,1,2\}^4 = \{i,j,i^\prime,j^\prime\mid 0\le i,j,i^\prime,j^\prime \le 2\};$$
endow it with the discrete Sigma algebra $$\mathcal{F}=\mathcal{P}(\Omega),$$ the set of all subsets of $\Omega$; and define the probability measure $\mathbb{P}$ by stipulating its value on each singleton to be
$$\mathbb{P}(\{i,j,i^\prime,j^\prime\}) = p(i,j;t)\,p(i^\prime,j^\prime;1/9).\tag{1}$$
The four random variables will be the canonical projections. This means that for a generic $$(i,j,i^\prime,j^\prime) =\omega \in \Omega,$$
let
$$X(\omega) = i,\ Y(\omega) =j,\ X^\prime(\omega)=i^\prime,\ Y^\prime(\omega)=j^\prime.$$
Because every subset of $\Omega$ is in $\mathcal F$, there is no need to check that these are all measurable functions: they are honest-to-goodness random variables.
By virtue of the product formula $(1)$, $(X,Y)$ is independent of $(X^\prime,Y^\prime)$, so it suffices to verify separately that the contingency table for $(X,Y)$ is given by $p(i,j;t)$ and that the table for $(X^\prime,Y^\prime)$ is given by $p(i,j;1/9)$--but that, too, is immediate from $(1)$. That completes the construction of $\left(\Omega, \mathcal{F}, \mathbb{P}\right)$ and the four random variables $(X,Y,X^\prime,Y^\prime)$ defined on it.