Here's an another approach solving the recurrrence relation
\begin{align*}
x_0&=3\\
x_1&=4\tag{1}\\
x_{n+1}&=x_{n-1}^2-nx_n\qquad\qquad n\geq 2
\end{align*}
But first a few words to your classification of this recurrence relation. You're right when you're saying it's neither a linear nor a non-linear homogeneous recurrence relation with constant coefficient. You could argue:
Type of recurrence relation:
- Since the constant term is 0 it's a homogeneous recurrence relation
- Since $x_{n-1}$ occurs squared it's a non-linear recurrence relation
- Since the coefficent of $x_{n}$ is $n$ it's a recurrence relation with non-constant coefficients
- Since $x_{n+1}$ is specified with the help of $x_n$ and $x_{n-1}$ there are two degrees of freedom and so it is a recurrence relation of order 2. We therefore need two initial values to fully specify the recurrence relation.
So, we can specify:
The recurrence relation (1) is a quadratic, homogeneous recurrence relation of order 2 with non-constant coefficients.
Now an alternative approach in three steps.
1.) Ansatz: $x_n$ is a polynomial $P$ in $n$
Since the initial values are constants and $x_{n+1}$ is defined as square of a former term and $n$ times another former term we could check if $x_n$ is a polynomial in $n$.
Attention: As @ChristianBlatter pointed out with a counter example in a comment below, it's not always the case that $x_n$ is a polynomial. It depends on the structure of the recurrence relation.
2.) The degree deg P
So, let's consider $x_n$ to be a polynomial $P(n)$ and try to determine the degree $d=\text{deg}P(n)$ of the polynomial $x_n$=$P(n)$. In order to do so, we rewrite the recurrence relation $(1)$ conveniently as
\begin{align*}
x_{n+1}+nx_n&=x_{n-1}^2\\
\text{or}\tag{2}\\
P(n+1)+nP(n)&=P^2(n-1)
\end{align*}
We observe
\begin{array}{rl}
\text{LHS has degree}&d+1\\
\text{RHS has degree}&2d
\end{array}
Since $d+1=2d$ we get $\text{deg}P=1$ and so we can choose the
3.) Ansatz: $x_n=P(n)$ with $\text{deg}P(n)=1$
\begin{align*}
x_n=an+b\qquad\qquad a,b\in\mathcal{R}
\end{align*}
With the help of the initial conditions $x_0=3$ and $x_1=4$ we find
\begin{align*}
x_0&=a\cdot0+b=3\\
x_1&=a\cdot1+b=4
\end{align*}
with the solution $a=1$ and $b=3$.
So, a closed form of the recurrence relation $(1)$ is
\begin{align*}
x_n=n+3\qquad\qquad n\geq 0
\end{align*}
