I am facing the following problem: Let $X_1,X_2 \sim \mathcal{N}(0,1)$, let $Z$ be r.v. independent of both $X_1,X_2$ s.t. $P(Z=+1)=P(Z=-1)=\frac{1}{2}$ Which of the following r.v. are still Gaussian: $$a)X_1+Z(X_2),\\ b)X_1+Z(X_2-X_1),\\ c)X_1+X_2+Z(X_1+X_2),\\ d)X_1+X_2+Z(X_1-X_2)$$
So far I have been able to prove that $Z(X_2)\sim \mathcal{N}(0,1)$ and thus $a)$ must be Gaussian $\sim \mathcal{N}(0,2)$. But, since $X_1+X_2$ and $X_1-X_2$ are all Gaussian, being linear combinations of Gaussians r.v., doesn't that reasoning apply to all of them?
You forgot to mention that $X_1$ and $X_2$ are independent and this is important for this question. In c) and d) it turns out that $X_1+X_2$ and $X_1-X_2$ are also independent. This a special property of standard normal distribution. Hence your conclusion that c) and d) are normal is correct. We can show that $X_1+Z(X_2-X_1)$ is not normal by computing its characteristic function which is $(\frac {1+e^{-2t^{2}}} 2) e^{-t^{2}/2}$ which is not a normal characteristic function. Hence b) is not normal.