Yes, it is possible; pick a nonzero element of $\mathbf{x}$, which must exist since $\mathbf{x}\neq 0$; let's say this nonzero element is $x_j$. Then define
$$\big(\mathbf{M}_{\mathbf{x}}\bigr)_{nm}=-\delta_{nm}(1-\delta_{nj})+\delta_{nm}\delta_{nj}\left(x_{j}^{-2}+x_{j}^{-2}\sum_{k\neq j}x_k^2\right).$$
Now you have the desired result,
$$\sum_{n,m}x_nx_m\big(\mathbf{M}_{\mathbf{x}}\bigr)_{nm}=1>0,$$
while $\mathbf{M}_{\mathbf{x}}$ is itself not positive definite.

This matrix is symmetric, if you want it to be nonsymmetric, simply add to  $\mathbf{M}_{\mathbf{x}}$ an arbitrary skew-symmetric matrix $\mathbf{A}$ and use that $\mathbf{x}^T (\mathbf{M}_{\mathbf{x}}+\mathbf{A})\mathbf{x} =\mathbf{x}^T \mathbf{M}_{\mathbf{x}}\mathbf{x}$.

<sub> I don't understand your second question "And how can I prove this statement without showing that $\mathbf{M}_{\mathbf{x}}$ is always positive definite?" To prove this you need to examine the function $f(\mathbf{x})$, without further knowledge of this function no progress can be made.</sub>