Solution:
Note that $k^{p-1} \equiv 0 \pmod{p}$ if $p$ divides $k$ and $k^{p-1} \equiv 1 \pmod{p}$ otherwise (by Fermat's little theorem). Then
$$0 \equiv 1^{p-1}+2^{p-1}+\cdots+2004^{p-1} \equiv 0 \cdot\left[\frac{2004}{p}\right]+1 \cdot\left(2004-\left[\frac{2004}{p}\right]\right) \pmod{p}$$
which implies
$$2004 \equiv \left[\frac{2004}{p}\right] \pmod{p}$$
(in particular, $p<2004$). Let $2004=qp+r$, where $0 \leq r \leq p-1$. Then $\left[\frac{2004}{p}\right]=\left[q+\frac{r}{p}\right]=q$ and $(1)$ is equivalent to $r \equiv q \pmod{p}$.

For $q<p$, this congruence gives $r=q$. Then
$$2004=(p+1)q \leq p^{2}-1$$
and therefore $p \geq 47$. Since $p+1$ divides $2004=3 \cdot 4 \cdot 167$, we get $p=2003$ which is a solution of the problem.

For $q \geq p$, we have that $2004 \geq pq \geq p^{2}$, i.e., $p \leq 43$. A direct verification of (1) shows that $p=17$ is the only solution in this case.