First note that odd dimensions the question of Euler characteristic $0$ is automatic, $M$ will embed in the orientable double cover of $\tilde{M}$, which will have $\chi = 0$ by Poincare Duality.

In even dimension = $2n$, we recall the following fact. If $M_{1},M_{2}$ are compact connected manifolds then $\chi(M_{1} \# M_{2}) = \chi(M_{1}) + \chi(M_{2}) - \chi(S^{2n}) = \chi(M_{1}) + \chi(M_{2}) - 2$.

To prove that some embedding into any manifold implies embedding in to Euler characteristic $0$ manifold, it is sufficient to show that any positive integer is equal to the Euler characteristic of some manifold of dimension $2n$, since we can do connect sums on the complement of the embedding $M \hookrightarrow \tilde{M}$ (It is easy to see that the embedding can be made so that this complement contains an open set) to shift the Euler characteristic of $\tilde{M}$ to the correct value.   

Recall that $\chi (\mathbb{R} \mathbb{P}^{2}) = 1$. For any positive in integer there is a compact $2$-manifold $S$ such that $\chi(S) = n$. Then $S \times \mathbb{R} \mathbb{P}^{2} \times ...  \times \mathbb{R} \mathbb{P}^{2} $ (where we take $n-1$-copies of $\mathbb{R} \mathbb{P}^{2}$ is a $2n$-manifold with $\chi = n$.