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.
Note that without any assumption on the singularities the answer to your question is yes. For instance, consider the hypersurface $Y = \{x_0^2+x_1^3+x_2^4\}\subset\mathbb{P}^3$. Then $Sing(Y) = [0:0:0:1]$. The projective tangent cone of $Y$ in the singular point is not reduced. Therefore, the singularity is not ordinary. Let $\pi:X\rightarrow\mathbb{P}^3$ be the blow-up of $[0:0:0:1]$. It is easy to check that the singular locus of the strict transform $\widetilde{Y}\subset X$ contains a curve.
On the other hand, if the singularities are ordinary this can not happen.
More precisely:
Let $W\subset Z\subset X$ be smooth projective varieties, and let $Y\subset X$ be a projective variety such that $Sing(Y) = Z$ and $Y$ has ordinary singularities along $Z$. Let $\pi_W:X_W\rightarrow X$ be the blow-up of $W$, and $Z_W$, $Y_W$ the strict transforms of $Z$ and $Y$ respectively. Then $Sing(Y_W) = Z_W$ and $Y_W$ has ordinary singularities along $Z_W$.
Here is the proof:
The inverse image via $\pi_W$ of $Z$ is given by $Z_W\cup E_W$, where $E_W$ is the exceptional divisor of $\pi_W$. Now, we may consider the blow-up $\pi_{Z_w}:X_{Z_W}\rightarrow X_W$ of $Z_W\cup E_W$ in $X_W$, and the blow-up $\pi_Z:X_Z\rightarrow X$ of $Z$ in $X$. Note that since $E_W$ is a Cartier divisor in $X_W$ its blow-up does not produce any effect. By Corollary 7.15 in Harshorne there exists a morphism $f:X_{Z_W}\rightarrow X_Z$ such that $\pi_Z\circ f = \pi_W\circ \pi_{Z_{W}}$. Therefore, the morphism $f$ must map the exceptional divisor $E_{Z_W}$ of $\pi_{Z_W}$ onto the exceptional divisor $E_{Z}$ of $\pi_Z$. Furthermore, $f$ contracts the strict transform $\tilde{E}_W$ of $E_W$ in $X_{Z_W}$ onto $\pi_{Z}^{-1}(W)\subset E_Z$.
Now, let $g:\widetilde{X}_Z\rightarrow X_Z$ be the blow-up of $\pi_{Z}^{-1}(W)$. By the universal property of the blow-up, see Proposition 7.14 Hartshorne, there exits a unique morphism $\phi:X_{Z_W}\rightarrow \widetilde{X}_Z$ such that $g\circ\phi = f$.
Note that since we just blew-up smooth subvarieties both $X_{Z_W}$ and $\widetilde{X}_Z$ are smooth with Picard number $\rho(X_{Z_W}) = \rho(\widetilde{X}_Z) = \rho(X)+2$. In particular, the birational morphism $\phi:X_{Z_W}\rightarrow \widetilde{X}_Z$ can not be a divisorial contraction. Notice that $\phi$ can not be a small contraction either because otherwise $\widetilde{X}_Z$ would be singular. We conclude that $\phi$ is a bijective morphism, and since both $X_{Z_W}$ and $\widetilde{X}_Z$ are smooth $\phi$ is an isomorphism.
Now, let $Y_W$ be the strict transform of $Y$ in $X_W$, and assume that $Z_W\subsetneqq Sing(Y_W)$. Therefore, the strict transform $Y_{Z_W}$ of $Y_W$ in $X_{Z_W}$ is singular, and since $g$ is just the blow-up of a smooth variety the image $(g\circ \phi)(Y_{Z_W}) = f(Y_{Z_W})\subset X_Z$ is singular as well. Note that $f(Y_{Z_W})\subset X_Z$ is nothing but the strict transform of $Y$ via $\pi_Z$, and since $Sing(Y) = Z$ and $Y$ has ordinary singularities along $Z$ the blow-up $\pi_Z$ resolves the singularities of $Y$. A contradiction. We conclude that $Sing(Y_W) = Z_W$. Finally, if the intersection $Y_{Z_W}\cap E_{Z_W}$ is not transversal then the intersection $Y_Z\cap E_Z$ is not transversal as well. But this can not happen because the singularities of $Y$ are ordinary. Therefore, $Y_W$ has ordinary singularities along $Z_W$.
Best Answer
I guess you are right... :)
It seems to me that this indeed fails quite often.
Let $d=\mathrm{codim}_XZ$ and $P=f^{-1}Z\subseteq \widetilde X$ the exceptional divisor. By the assumptions $P\to Z$ is a $\mathbb P^{d-1}$-bundle.
First note that as long as $d\leq 2$, then the statement is probably true for the simple reason that if $V\neq X$, then $\dim (V\cap Z)\leq \dim V-1$ and hence the largest dimensional part of the pull-back of the Segre class $s(V\cap Z, V)$ has dimension at most $\dim V$ and hence that's the only component that makes a meaningful appearance in the formula for $f^*[V]$.
So, let's go to $d=3$. In this case $P\to Z$ is a $\mathbb P^{2}$-bundle. Now let $V\subseteq X$ be a surface such that $C=V\cap Z\subseteq V$ is a Cartier divisor in $V$. Then the Segre class in question is $$ s(C,V)=[C]-[C]^2. $$ Since we have a nice blow up, the "mysterious" excess normal bundle is just the relative tangent bundle $T_{P/Z}$, but this actually doesn't really matter, all we need is that there is a short exact sequence, $$ 0\to \mathscr O_P(-1) \to f^*N \to E\to 0, $$ where $N=N_{Z/X}$ is the normal bundle of $Z$ in $X$.
So we need the class $\left(c(E)\cdot_P f^*([C]-[C]^2)\right)_2$.
Observe that $f^*[C]$ has dimension $3$ and $f^*[C]^2=f^*([C]\cdot_V[C])$ has dimension $2$, so we need to intersect the first with $c_1(E)=c_1(f^*N)-c_1(\mathscr O_P(-1) )$ and the second with $c_0(E)=1$. Using that $$ c_1(f^*N)\cdot_P f^*[C]= f^*(c_1(N)\cdot_Z [C]), $$ we get that $$ \left(c(E)\cdot_P f^*([C]-[C]^2)\right)_2= f^*(c_1(N)\cdot_Z [C]-[C]^2)+ c_1(\mathscr O_P(1))\cdot_P f^*[C]. $$ So, it seems that if the intersection $C=V\cap Z$ is such that
then the above class will not be effective. Note that these choices make the $f^*$ part of the class negative effective while the other class is "horizontal", so it is unlikely to cancel the "vertical" classes, but in any case one can probably play around with $V$ and $Z$ to make this more precise.
It seems that if the codimension of $Z$ is even higher and the intersection $V\cap Z$ is still large in $V$, then there is even more that can go wrong.