What is the PRG period of stream ciphers such as RC4 or Salsa20? I am confused about how long a stream cipher can be used before you should change the key. To be concrete, let me use the stream cipher based on RC4 as an example.

Let's say I want to encrypt a very long message. I pick a key with 128 bits and start encrypting using the RC4 stream cipher. How many rounds does RC4 have to run before its PRG starts over again? How about Salsa20: how long can that run with the same key before running the risk of leaking information?

I realize that as a practical matter the period will probably be far longer than any real-world message, but I am still interested in knowing the bound.
The internal state of RC4 consists of a shuffled 256-element array and two pointers into that array.  Thus, there are a total of $$256! \times 256^2 \approx 2^{1700.00}$$ possible states.  Since the state update function of RC4 is reversible, it acts as a permutation on this set of possible states, so that every starting state will eventually recur after sufficiently many iterations.

How many is sufficiently many?  Well, if we assume that the update function behaves like a random permutation (which it, of course, does not, but it's a good first approximation), then the expected cycle length is approximately $2^{1700}/2 = 2^{1699}$ iterations(!).  Indeed, the probability that the cycle length starting from a random state is at least $k$ iterations is approximately $1 - k/2^{1700}$; this means that hitting a cycle of less than, say, $2^{200}$ iterations should happen less than once in $2^{1700-200} = 2^{1500}$ initializations, i.e. basically never within the lifetime of the universe.

Of course, as noted, the RC4 state update function is not a random permutation.  For example, there's a known class of $254!$ short cycles of $256^2-256 = 65280$ states each; fortunately, the standard RC4 key setup is guaranteed never to hit them.  For more information on the actual cycle structure of RC4, see e.g. "Cryptanalysis of RC4-like Ciphers" by S. Mister and S. E. Tavares.