Find all $n$ such that $\gcd(3n-4, n^2+1)=1$

Yes, the Euclidean algorithm is a good starting point. In particular recall these properties of the $\gcd$.

Hint. Since $3n-4$ is not divisible by $3$, we may consider $$\begin{align}\gcd(3n-4, n^2+1)&=\gcd(3n-4, 3n^2+3)\\&=\gcd(3n-4, (3n-4)(n+1)+n+7)\\&=\gcd(3n-4,n+7)\end{align}$$ Can you take it from here?

P.S. At end you will see that your remark about the common divisor $5$ is "almost" correct: the $\gcd$ can be $1$, $5$ or $25$.