1. Initial Setup and Definitions:
Given $a_0 > 1$, the sequence $a_0, a_1, a_2, \ldots$ is defined such that for all $k > 0$, $a_k$ is the smallest integer greater than $a_{k-1}$ which is relatively prime to all the earlier terms in the sequence. We need to find all $a_0$ for which all terms of the sequence are primes or prime powers.

2. Lemma 1:
Every prime divides a term in the sequence.
- Proof: Take any prime $p$. Suppose $k$ is the least integer such that $a_1 \le p^k$. Now let $z$ be the least such integer such that $a_z \ge p^k$. If $a_z \neq p^k$, then $p$ divides one of $a_1, a_2, \ldots, a_{z-1}$. But then we're done.

3. Corollary:
If $p$ is prime, then $p^{\lceil \log_p{a_1} \rceil}$ is one of the $a_i$.

4. Sequence Behavior:
It follows that for sufficiently large $n$, the $a_n$ are just a bunch of consecutive primes. Note that by the corollary, if $a_n > a_0^2$, then $a_n$ is prime.

5. Prime Product Argument:
We can pick two primes $p$ and $q$ such that $pq \in [a_1, a_1^2]$ but $p^{\lceil \log_p{a_1} \rceil}, q^{\lceil \log_q{a_1} \rceil} > pq$.
- By Bertrand's Postulate, we can find a prime $p$ such that $\frac{\sqrt{a_1}}{2} - 1 < p < \sqrt{a_1}$ when $a_1 \ge 16$.
- Let $\frac{\sqrt{a_1}}{p} = z$. Then we can also find a prime $q$ such that $z\sqrt{a_1} < q < 2z\sqrt{a_1}$.

6. Contradiction:
- Clearly, $pq > a_1$. However, $p^{\lceil \log_p{a_1} \rceil} \ge p^3 > pq$.
- We also have $q^{\lceil \log_q{a_1} \rceil} = q^2 > pq$.
- Thus, it follows that $pq$ must be one of the $a_i$, leading to a contradiction. Therefore, $a_1 < 16$.

7. Case Analysis:
- Checking which values of $a_1$ less than 16 work involves casework.
- Further analysis suggests that $a_0$ must be of the form $2^{2^n}$ except in some exceptional cases.

The final answer is $\boxed{ a_0 }$ must be of the form $2^{2^n}$.