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}$.
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.