How do I find $g$ given $g^r \bmod p$ How can $g$ be derived from $c = g^r \bmod p$ ?

$g$ and $r$ are not known, but $c$ and $p$ is. And oracle can provide many $c$ but the $r$ and $p$ is always random. 

I think this is somewhat related to Decisional Diffie Hellman but I am not sure where to go from there, as the $p$ is always random.
Here's a solution:

If we assume many pairs $(c_i,p_i)$, and all the $p_i$ are primes (because  often the letter $p$ is used when talking about primes, and you relate to the DLOG problem in your question where the modulus is also prime), then we can use this method:

We ignore all the $c_i$. For every $p_i$ we find one generator $g_i$ of the entire group. And then we use the Chinese Remainder Theorem to find $g$, which fullfills $g = g_i \mod p_i$ for every $p_i$. Now $g$ is a generator for every subgroup, and therefore for every $p_i$ there exists some $r_i$, s.t. $c_i = g^{r_i}$. This has nothing to do with the DLOG problem, it is just finding a generator for several groups.



But if we assume any random $p_i$, then we also need a closes look at the numbers, and we need to consider all the $c_i$ as well:


First, we need to check which $c_i$ are not coprime to their respective $p_i$. If $ggt(c_i,p_i) = a$, then we already know that $a$ is a prime factor of $g$, which is like the equation $g  = 0 \mod a$ in the CRT.
Then, instead of looking at the individual $p_i$, we look at all the prime factors of all $p_i$ instead, which are coprime to $g$. And we need to take the prime powers of those factors into account, but it's quite straight forward as well.