What you've said so far is correct, but the fact that the group is cyclic of order $p-1$ is significantly harder. You'll need some real idea here; it's not a matter of just following your nose.
One standard approach is to prove the Cyclicity Criterion: a group $G$ of finite order $n$ is cyclic $\iff$ for each divisor $d$ of $n$ there are at most $d$ elements $x$ with $x^d = 1$ (the identity element). This is generally proved using a counting argument, and it is helpful to know that $\sum_{d \mid n} \varphi(d) = n$, where $\varphi(d) = \# (\mathbb{Z}/d\mathbb{Z})^{\times}$ is the number of integers $1 \leq e \leq d$ with $\gcd(e,d) = 1$.
With that in hand you should observe that $\mathbb{Z}/p\mathbb{Z}$ is a field, and thus the number of roots of the polynomial $x^d - 1 = 0$ in it is at most $d$. This argument ends up showing a little more: any finite subgroup of the multiplicative group of a field is cyclic.
P.S.: If I tell you that the result is often called "existence of primitive roots modulo $p$", that may help you look it up in many standard introductory texts on algebra and/or number theory.
The general way to find all homomorphism $\mathbb Z_n\to G$ for an arbitray abelian group $G$ is the following: Suppose $\phi:\mathbb Z_n\to G$ is a group homomorphism, as you said, it is determined by the image of $1$, so the question really is which choices of $g\in G$ give a homomorphism $\mathbb Z_n\to G$ when picked as the image of $1$?
For homomorphisms $\psi:\mathbb Z\to G$, this is easy: Pick any $g\in G$, let $\psi(x)=xg$ and just check $$\psi(x+y)=(x+y)g=xg+yg=\psi(x)+\psi(y).$$
Now what could go wrong? The subtle thing that happens here is better exposed, when we write $G$ as a multiplicative group. The definition of $\psi$ becomes $\psi(x)=g^x$ and the calculation becomes $$\psi(x+y)=g^{x+y}=g^x g^y =\psi(x)\psi(y).$$
The important fact: $g^x$ is defined for $x\in\mathbb Z$, that's why $\mathbb Z\to G$ is easy.
Going back to $\phi:\mathbb Z_n\to G$ and sticking to multiplicative notation, it is tempting to just choose $\phi(1)=g$ and define $\phi(x)=g^x$. But here you run into trouble: When $x\in\mathbb Z_n$, what is $g^x$ supposed to mean? Remember that $x\in\mathbb Z_n$ really is a coset of $n\mathbb Z$ in $\mathbb Z$, consisting of all elements of the form $x+kn$ with $k\in\mathbb Z$ and that $\mathbb Z_n$ is really just a shorthand for $\mathbb Z/n\mathbb Z$, the set of all cosets equipped with addition.
What you are really doing is defining $\psi:\mathbb Z\to G$ by $\psi(x)=g^x$ (which is fine) and then look at the induced map $\phi:\mathbb Z_n\to G$ with $\phi(x+n\mathbb Z)=g^x$ for all $x\in\mathbb Z$. Now the definition depends on the representative $x$ of the coset $x+n\mathbb Z$. For the map to be even well defined, it has to be independent of the choice of the representative: If $x+n\mathbb Z=y+n\mathbb Z$, so $x-y=kn$ for some $k\in \mathbb Z$, we want $g^x=g^y$, so $1=g^{x-y}=g^{kn}$. Thus, for $\phi$ to be well defined, we need $g^{kn}=1$ for all $k\in\mathbb Z$: The order of $g$ needs to be a divisor of $n$. When this is the case, the same calculation as above reveals that $\phi$ is not only well defined, but a well defined group homomorphism.
Now that we know, that we can pick any $g\in G$ with order diving $n$, the example $\mathbb Z_4\to\mathbb Z_2\oplus\mathbb Z_2$ is a quick one: All elements of $\mathbb Z_2\oplus \mathbb Z_2$ are of order $1$ or $2$, both are divisors of $4$, so we can pick any of them.
Best Answer
You're on to a good start. An automorphism of a cyclic group is uniquely and completely determined by the image of any fixed generator, and that image must itself be a generator. That proves to you indeed that $Aut(\mathbb Z_8)$ has four elements.
Now, to go on, you just need to distinguish between the two possibilities for a group of order $4$. It is either isomorphic to $\mathbb Z_4$ or to $\mathbb Z_2 \times \mathbb Z_2$. There are four possibilities for generators of $Aut(\mathbb Z_8)$, so you can try each of them and see if it generates the whole group or not. You'll quickly find the correct answer, proving the result.