I had the following set of simultaneous equations in $\mathbb{Z}_7$.
$$3x+5y=1$$ $$4x-5y=5$$
Now adding them we get
$$7x=6$$
And this has no integer solution in $x$ since $7$ and $6$ are coprime.
Would it then be sufficient and correct to then conclude that the system has no solutions over $\mathbb{Z}_7$?
Furthermore, is there a way of determining if a set of simultaneous equations has a solution over some $\mathbb{Z}_n$ without explicitly trying to find solutions and discovering that the system does not work?
Just use the usual tools from linear algebra. You have a system of 2 linear equations in $\mathbb{Z}_7$. Just take the determinant!
$$\begin{vmatrix}3 & 5 \\ 4 & -5\end{vmatrix} = -15-20=-35 = 0 \pmod 7$$
Zero! So, the rank of system's matrix is 1. What about the augmented matrix $\begin{pmatrix}3 & 5 & 1 \\ 4 & -5 & 5\end{pmatrix}$?
$$\begin{vmatrix}3 & 1 \\ 4 & 5\end{vmatrix} = 15 - 4 = 11 = 4 \pmod 7$$
It has a non-zero minor of maximum rank, so has rank 2. Since the ranks differ, the system is inconsistent, and has no solutions.