When can a random variable be written as a sum of two iid random variables? Suppose $X$ is a random variable; when do there exist two random variables $X',X''$, independent and identically distributed, such that $$X = X' + X''$$ 
My natural impulse here is to use Bochner's theorem but that did not seem to lead anywhere. Specifically, the characteristic function of $X$, which I will call $\phi(t)$, must have the property that we can a find a square root of it (e.g., some $\psi(t)$ with $\psi^2=\phi$) which is positive definite. This is as far as I got, and its pretty unenlightening - I am not sure when this can and can't be done. I am hoping there is a better answer that allows one to answer this question merely by glancing at the distribution of $X$.

I think your characteristic function approach is the reasonable one.  You take the square root of the characteristic function (the one that is $+1$ at 0), take its Fourier transform, and check that this is a positive measure.  In the case where $X$ takes only finitely many values, the characteristic function is a finite sum of exponentials with positive coefficients, and the criterion becomes quite manageable: you need the square root to be a finite sum of exponentials with positive coefficients.  More general cases can be more difficult.
