You should understand how potentials work and how they relate to forces. It is not as simple as saying that information travels at the speed of light. As I will show below, potential can change instantaneously everywhere (but that doesn't mean that information is traveling faster than light.
Lets begin with the Maxwell's equations:
$$
\nabla \cdot \mathbf{E} = \frac{\rho(\mathbf{x},t)}{\epsilon_o} \\
\nabla \cdot \mathbf{B} = 0 \\
\nabla \times \mathbf{E} = -\frac{\partial \mathbf{B}}{\partial t} \\
\nabla \times \mathbf{B} = \mu_o \mathbf{J} + \mu_o \epsilon_o
\frac{\partial \mathbf{E}}{\partial t}$$
Since $\nabla \cdot \mathbf{B} = 0$ we can write $\mathbf{B} = \nabla \times \mathbf{A}$ where $\mathbf{A}$ is a vector field that we name the vector potential. Using this in the third Maxwell equation we can write:
$$\nabla \times \left(\mathbf{E} +\frac{\partial \mathbf{A}}{\partial t}\right)=0$$
since we can freely exchange the curl and the partial derivative over time as they are independent. Then using the fact that the curl of a gradient is 0 we define the scalar potential V as:
$$\mathbf{E} +\frac{\partial \mathbf{A}}{\partial t} = -\nabla V \\
or\\
\mathbf{E} =-\frac{\partial \mathbf{A}}{\partial t} -\nabla V
$$
You will notice that so far we have only used the second and third Maxwell's equations. And we have the scalar and vector potential that can give the electric and magnetic field. But the expressions for the potentials that we have obtained need prior knowledge of the fields to be evaluated. To get around this we will now use the remaining first and fourth of the Max's equations.
By doing the substitutions for $\mathbf{E}$ and $\mathbf{B}$ in terms of $\mathbf{A}$ and V in these equations we get:
$$-\nabla^2 V -\frac{\partial}{\partial t} (\nabla \cdot \mathbf{A}) = \frac{\rho}{\epsilon_o}\\
and\\
\left(\nabla^2 \mathbf{A} - \mu_o \epsilon_o \frac{\partial^2 \mathbf{A}}{\partial t^2}\right)-\nabla\left(\nabla \cdot \mathbf{A} + \mu_o \epsilon_o \frac{\partial V}{\partial t}\right) = -\mu_o \mathbf{J}
$$
So we have these two PDE's that contain all the information of Max's equations. I guess you could say that they are the integral form of Max's equations. You might be getting tired now. But don't worry, we are getting there. To solve these nasty PDE's we need to make some gauge choices.
So, before I can show you how you should think about potential due to changing charge distributions, I must talk about gauges. There is something called the gauge freedom which basically means that these PDE's don't uniquely specify the potentials. In fact you can add the gradient of any scalar valued function to the vector potential and subtract its partial time derivative from the scalar potential without changing the fields. What this entails is that you can choose the value of $\nabla \cdot \mathbf{A}$ to be equal to 0(Coulomb gauge) or $-\mu_o\epsilon_o \frac{\partial V}{\partial t}$ (Lorentz gauge) among other things(other gauges).
So lets work with Coulomb gauge because it will illustrate my point. Setting the $\nabla \cdot \mathbf{A} = 0$ in the first PDE we get:
$$\nabla^2 V = -\frac{\rho(\mathbf{x}', t)}{\epsilon_o}$$
which you can solve using Green's functions to get:
$$V(\mathbf{x},t) = \frac{1}{4 \pi \epsilon_o} \int \frac{\rho(\mathbf{x}', t)}{|\mathbf{x}'-\mathbf{x}|} d^3 \mathbf{x}'$$
So you see that the potential at $\mathbf{x}$ at time $t$ depends on the charge density at $\mathbf{x}'$ at time $t$. So, a change in the charge distribution will update the scalar potential immediately everywhere. Now, you may be worried that this will break causality. But that won't happen because the vector potential is time dependent unlike the scalar one and to calculate the field (which is the only measurable quantity) you need the vector potential. So, even though a changing charge density on the surface may affect a moving charged particle in a Faraday cage(it doesn't block magnetic fields), one cannot really talk about gradients in the scalar potential due to time dependence as you are implying (at least in Coulomb gauge).