Is potential instantaneous, unlike fields which take time to alter depending on their mediators? If there's a Charge distribution 4 Light-years away, static, we have a distinct value of Electric Field and Electric Potential where I'm measuring it through some wack-a-doodle apparatus at my home on earth.
Suppose I changed that charge distribution in an instant , it will take 4 years for the apparatus at my home to detect there's a change in Electric Field because photons are the mediators of the Electric Forces and Fields!
But what bout the Electric Potential? Is its change instantaneous? Or will it take 4 years? Or more? Or less?
If it's instantaneous, how so? Because the derivative of something instantaneous must not be taking 4 years for propagation!
If it's 4 years or more or less, how so? Photons have nothing to do with Potentials! Or does it?
And what is the qualitative definition of potential?
I am looking for a deeper answer, rather than just "potential is the ability to do work".
 A: First, a personal polemic: I caution against thinking of photons at all when doing classical electrodynamics. A photon is really not a well-defined concept in this context, and my experience is that it lends itself to conceptual misunderstandings. 
The retarded time-dependence of the electric and magnetic fields on the source distribution that you've pointed out does not necessarily hold for the potentials. Indeed, the potentials are gauge-dependent, and by a choice of gauge we may partially divorce the potentials from the time-retardation to which the fields are subject. As Griffiths points out in his EM text (p. 441 in the 4th edition):

There is a very peculiar thing about the scalar potential in the Coulomb gauge: it is determined by the distribution of charge right now. If I move an electron in my laboratory, the potential $V$ on the moon immediately records this change. That sounds particularly odd in the light of special relativity, which allows no message to travel faster than $c$. The point is that $V$ by itself is not a physically measurable quantity-all the man in the moon can measure is $\mathbf E$, and that involves $\mathbf A$ as well (Eq. 10.3). Somehow it is built into the vector potential (in the Coulomb gauge) that whereas $V$ instantaneously reflects all changes in $\rho$, the combination $-\nabla V - \partial \mathbf{A}/\partial t$ does not; $\mathbf E$ will change only after sufficient time has elapsed for the "news" to arrive.

However, this doesn't have anything to do with photons. In quantum electrodynamics, one typically quantizes the EM four-potential $A_\mu$ (see this answer for why) rather than the fields. So, photons are quanta of the potential rather than the field, and it is not true that "Photons have nothing to do with Potentials"
