So here's what I think should work (it is based on my comments above). I'm going to assume for simplicity that the variety means irreducible (just to avoid some silly complications, it is not really needed).
Start with $f : Z \to X$ projective and birational (as discussed above, $Z$ is contructed via Chow's Lemma). We don't know that $X$ is quasi-projective, so we can't apply Hartshorne II, 7.11 and thus immediately argue that $Z$ is itself a blow-up.
Set $U_i$ to be an open affine (or even quasi-projective) cover of $X$ and fix $V_i = f^{-1}(U_i)$. On each chart $U_i$, set $J_i$ to be an ideal sheaf such that $f_i : V_i \to U_i$ is the blow-up of $J_i$.
For each $i$, fix $I_i$ to be a (generically non-zero) ideal sheaf on $X$ such that $I_i |_{U_i} = J_i$.
Now fix $I = \prod_i I_i$. This is an ideal sheaf on $X$. On each open chart $U_i$, it is equal to $J_i \cdot \prod_{j \neq i} I_j|_{U_i}$.
Set $\pi : Y \to X$ to be the blow-up of $I$. We wish to show that $\pi$ factors through $f$, and is in fact a blow-up of $Z$, and so $Y$ is indeed projective. Set $W_i = \pi^{-1}(U_i)$.
All schemes involved are separated, and so to verify that $Y \to X$ actually factors through $Z \to X$, it is sufficient to work locally, so work on a chart $U_i$.
There we are comparing the blow-up of $J_i$ with the blow-up of $J_i \cdot \prod_{j \neq i} I_j|_{U_i} = J_i \cdot K_i$. $V_i$ is the blow-up of $J_i$ and $W_i$ is the blow-up of $J_i \cdot K_i$. However, I claim it is a straightforward exercise to verify that $W_i$ is the same as the blow-up of the ideal sheaf $(J_i \cdot K_i) \cdot \mathcal{O}_{V_i}$.
Let me give a hint as to how to do this.
Set $R = \Gamma(U_i, \mathcal{O}_X)$, set $J_i = (x_1, \dots, x_n)$ and $K_i = (y_1, \dots, y_m)$. Then the blow-up of $J_i$ is covered by affine charts $U_{i,l} = \text{Spec} R[x_1/x_l, \dots, x_n/x_l]$ where the gluings are the obvious ones. Likewise the blowup of $J_i \cdot K_i$ is covered by charts $U_{i,s,t} = \text{Spec} R[(x_1y_1)/(x_s y_t), \dots, (x_1y_m)/(x_s y_t), \dots, (x_ny_m)/(x_s y_t) ]$. Which are easily checked to be the blow-ups of $U_{i,s}$ at $(J_i \cdot K_i) \cdot R[x_1/x_l, \dots, x_n/x_l]$ (unless I've completely forgotten how to do this).
This sort of computation should be viewed as a generalization of the fact that the blow-up of an ideal is the same as the blow-up of a power of an ideal.
But this proves everything I claimed, right? $Y$ is exactly the blow-up of $Z$ at $I \cdot \mathcal{O}_Z$, and so $Y$ is projective, and is the blow-up of some ideal sheaf.
Of course, writing this as a sequence of blow-ups at subvarieties (and not subschemes/ideals) is probably much much harder.
