Bill and Willie have (of course) given correct answers in terms of the holonomy of the given torsion-free connection $\nabla$ on the $n$-manifold $M$. However, it should be pointed out that, practically, it is almost impossible to compute the holonomy of $\nabla$ directly, since this would require integrating the ODE that define parallel transport with respect to $\nabla$. Even though they are linear ODE, for most connections given explicitly by some functions $\Gamma^i_{jk}$ on a domain, one cannot perform their integration.
Although, as Bill pointed out, you cannot always tell from local considerations whether $\nabla$ is a metric connection, you can still get a lot of information locally, and this usually suffices to determine the only possibilities for $g$. The practical tests (carried out essentially by differentiation alone) were of great interest to the early differential geometers, but they don't get much mention in the modern literature.
For example, one should start by computing the curvature $R$ of $\nabla$, which is a section of the bundle $T\otimes T^\ast\otimes \Lambda^2(T^\ast)$. (To save typing, I won't write the $M$ for the manifold.)
Taking the trace (i.e., contraction) on the first two factors, one gets the $2$-form $tr(R)$. This must vanish identically, or else there cannot be any solutions of $\nabla g = 0$ for which $g$ is nondegenerate. (Geometrically, $\nabla$ induces a connection on $\Lambda^n(T^\ast)$ (i.e., the volume forms on $M$) and $tr(R)$ is the curvature of this connection. If this connection is not flat, then $\nabla$ doesn't have any parallel volume forms, even locally, and hence cannot have any parallel metrics.)
To get more stringent conditions, one should treat $g$ as an unknown section of the bundle $S^2(T^\ast)$, pair it with $R$ (i.e., 'lower an index') and symmetrize in the first two factors, giving a bilinear pairing $\langle g, R\rangle$ that is a section of $S^2(T^\ast)\otimes \Lambda^2(T^\ast)$. By the Bianchi identities, the equation $\langle g, R\rangle = 0$ must be satisfied by any solution of $\nabla g = 0$. Notice that these are linear equations on the coefficients of $g$. For most $\nabla$ when $n>2$, this is a highly overdetermined system that has no nonzero solutions and you are done. Even when $n=2$, this is usually $3$ independent equations for $3$ unknowns, and there is no non-zero solution.
Often, though, the equations $\langle g, R\rangle = 0$ define a subbundle (at least on a dense open set) of $S^2(T^\ast)$ of which all the solutions of $\nabla g= 0$ must be sections. (As long as $R$ is nonzero, this is a proper subbundle. Of course, when $R=0$, the connection is flat, and the sheaf of solutions of $\nabla g = 0$ has stalks of dimension $n(n{+}1)/2$.) The equations $\nabla g = 0$ for $g$ a section of this subbundle are then overdetermined, and one can proceed to differentiate them and derive further conditions. In practice, when there is a $\nabla$-compatible metric at all, this process spins down rather rapidly to a line bundle of which $g$ must be a section, and one can then compute the only possible $g$ explicitly if one can take a primitive of a closed $1$-form.
For example, take the case $n=2$, and assume that $tr(R)\equiv0$ but that $R$ is nonvanishing on some simply-connected open set $U\subset M$. In this case, the equations $\langle g, R\rangle = 0$ have constant rank $2$ over $U$ and hence define a line bundle $L\subset S^*(T^\ast U)$. If $L$ doesn't lie in the cone of definite quadratic forms, then there is no $\nabla$-compatible metric on $U$. Suppose, though, that $L$ has a positive definite section $g_0$ on $U$. Then there will be a positive function $f$ on $U$, unique up to constant multiples, so that the volume form of $g = f\ g_0$ is $\nabla$-parallel. (And $f$ can be found by solving an equation of the form $d(\log f) = \phi$, where $\phi$ is a closed $1$-form on $U$ computable explicitly from $\nabla$ and $g_0$. This is the only integration required, and even this integration can be avoided if all you want to do is test whether $g$ exists, rather than finding it explicitly.) If this $g$ doesn't satisfy $\nabla g = 0$, then there is no $\nabla$-compatible metric. If it does, you are done (at least on $U$).
The complications that Bill alludes to come from the cases in which the equations $\langle g, R\rangle = 0$ and/or their higher order consequences (such as $\langle g, \nabla R\rangle = 0$, etc.) don't have constant rank or you have some nontrivial $\pi_1$, so that the sheaf of solutions to $\nabla g = 0$ is either badly behaved locally or doesn't have global sections. Of course, those are important, but, as a practical matter, when you are faced with determining whether a given $\nabla$ is a metric connection, they don't usually arise.
There are trivial examples that arise just by taking products of irreducible Einstein metrics with different Einstein constants. Whether an irreducible example exists is a much harder question. I do not know the answer to that, but I can think about it. (However, see below, where I answer this question.)
Of course, no such irreducible example can be Riemannian, and I guess, from your statement about the Lorentzian case, it can't be Lorentzian either, though I don't see that immediately.
In light of this, I guess the first case to try would be to see whether or not there could be one in dimension $4$ that is of type $(2,2)$. (See Addition 1.)
Addition 1: Indeed, there is an irreducible example in dimension $4$ of type $(2,2)$. Consider the $6$-dimensional Lie group $G$ with a basis for left-invariant forms satisfying the structure equations
$$
\begin{aligned}
d\omega^1 &= - \alpha\wedge\omega^1 - \beta \wedge \omega^2 \\
d\omega^2 &= \phantom{-} \beta\wedge\omega^1 - \alpha \wedge \omega^2\\
d\omega^3 &= \phantom{-} \alpha\wedge\omega^3 - \beta \wedge \omega^4 \\
d\omega^4 &= \phantom{-} \beta\wedge\omega^3 + \alpha \wedge \omega^4\\
d\alpha &= c\ \bigl(\omega^3\wedge\omega^1+\omega^4\wedge\omega^2\bigr)\\
d\beta &= c\ \bigl(\omega^4\wedge\omega^1-\omega^3\wedge\omega^2\bigr)\\
\end{aligned}
$$
where $c\not=0$ is a constant.
Let $H$ be the subgroup defined by $\omega^1=\omega^2=\omega^3=\omega^4=0$ and let $M^4 = G/H$. Then the above structure equations define a torsion-free affine connection $\nabla$ on $M^4$ that satisfies
$$
\mathrm{Ric}(\nabla) = -4c\ (\omega^1\circ\omega^3+\omega^2\circ\omega^4)
$$
while both $h = \omega^1\circ\omega^3+\omega^2\circ\omega^4$ and $g = \omega^1\circ\omega^4-\omega^2\circ\omega^3$ are $\nabla$-parallel. Thus, $g + \lambda h$ is an example of the kind you want for any nonzero constant $\lambda$.
Addition 2: Upon further reflection, I realized that this example points the way to a large number of other examples, all of split type, and most having irreducibly acting holonomy as soon as the (real) dimension gets bigger than $4$.
The reason is that the above example is essentially a holomorphic Riemannian surface of nonzero (but real) constant curvature regarded as a real Riemannian manifold by taking the real part of the holomorphic quadratic form, i.e., $Q = (\omega^1+i\ \omega^2)\circ(\omega^3-i\ \omega^4) = h - i\ g$. (The group $G$ in the above example turns out to just be $\mathrm{SL}(2,\mathbb{C})$ and $H\simeq \mathbb{C}^\times$ is just a Cartan subgroup.)
Now, the same phenomenon occurs in all dimensions: Let $(M^{2n},Q)$ be a holomorphic Einstein manifold with a nonzero real Einstein constant and write $Q = h - i\ g$ where $h$ and $g$ are real quadratic forms. Then $(M,h)$ will be an Einstein manifold of type $(n,n)$ (with a nonzero Einstein constant) and $g$ will be parallel with respect to the Levi-Civita connection of $h$. Thus, all of the split metrics $g+\lambda\ h$ for $\lambda$ real will have the same Levi-Civita connection as $h$ and none of them will be Einstein. If the (holomorphic) holonomy of $Q$ is $\mathrm{SO}(n,\mathbb{C})$, then the holonomy of $h$ will be $\mathrm{SO}(n,\mathbb{C})\subset\mathrm{SO}(n,n)$, which acts $\mathbb{R}$-irreducibly on $\mathbb{R}^{2n}=\mathbb{C}^n$ when $n\ge3$.
(Constructing examples of non-split type might be interesting$\ldots$)
Addition 3: By examining the Berger classification (suitably corrected by later work), one can see that, if $M$ is simply connected and if $h$ is a non-symmetric pseudo-Riemannian metric on $M$ with irreducibly acting holonomy whose space of $\nabla$-parallel symmetric $2$-tensors has dimension greater than $1$, then the dimension of $M$ must be even, say, $2n$, and the holonomy of the metric $h$ must lie in $\mathrm{SO}(n,\mathbb{C})$. Of the possible irreducible holonomies in this case, only the subgroups $\mathrm{SO}(n,\mathbb{C})$ and $\mathrm{Sp}(m,\mathbb{C})\cdot\mathrm{SL}(2,\mathbb{C})$ (when $n=2m$) can occur if the metric is to be Einstein with a nonzero Einstein constant. Both of these cases do occur, and, in each case, the space of $\nabla$-parallel symmetric $2$-tensors has dimension exactly $2$. Thus, the construction outlined in Addition 2 gives all of the examples of desired pairs $(h,g)$ for which the holonomy is irreducible and that are not locally symmetric.
To make sure that we get the full list of examples with irreducible holonomy, we'd have to examine Berger's list of irreducible pseudo-Riemannian symmetric spaces for other possible candidates. (I suspect that, even there, the examples will turn out to be holomorphic metrics in disguise, but I have not yet checked Berger's list to be sure.)
The case in which the metric is irreducible but the holonomy is not remains, and it may not be easy to resolve with known technology.
Best Answer
NB: I'm combining my previous comments into an answer, because I believe that this is better than leaving them scattered.
As another commenter has pointed out, the skew-symmetric part of the Ricci tensor is the obstruction to there being a $\nabla$-parallel volume form in the first place. To see this, consider the first Bianchi identity: $R^i_{jkl}+R^i_{klj}+R^i_{ljk}=0$. Set $i=j$ and sum to get $R^i_{ikl}+R^i_{kli}+R^i_{lik}=0$, which becomes $R^i_{ikl}=R^i_{kil}-R^i_{lik}$. Now $\Omega = \frac12 R^i_{ikl}\ dx^k\wedge dx^l$ is the curvature of the connection induced by $\nabla$ on the top exterior power of the cotangent bundle, and $\frac12(R^i_{kil}{-} R^i_{lik})dx^k\wedge dx^l$ is the skew-symmetric part of the Ricci tensor. Thus, the vanishing of the skew-symmetric part of Ricci is equivalent to the flatness of this induced connection on the top exterior power.
Assume now that the Ricci curvature is symmetric, so that there is a (local) $\nabla$-parallel volume form, say, $\Upsilon$. Then the Ricci curvature has the following interpretation: Let $\exp_p:T_pM\to M$ be the exponential map of $\nabla$ based at $p$. Then $$ \exp^\ast_p(\Upsilon)=(1 - \tfrac13 R_{ij} x^ix^j + \cdots)\ dx^1\wedge dx^2\wedge\cdots\wedge dx^n, $$
where $\exp^\ast_p\bigl(\mathrm{Ric}(\nabla)\bigr)_p = R_{ij}\, dx^idx^j$. (Here, the $x^i$ are any linear coordinates on $T_pM$ centered at $0_p$ that are $\Upsilon$-unimodular at $0_p$.) Thus, Ric gives the deviation of the parallel volume form from the exponentially flat one. (This makes sense, even though you can't define 'geodesic balls' without a metric. You still compare the volume of open neighborhoods of $p$ with respect to the two 'natural' volume forms.)