Will Coulomb's law be valid always?
Coulomb's law is only valid in Electrostatics. In other words, you cannot ask questions like "What would happen if one of the charges is moved (or disappears)?" and hope to find a sensible answer using Coulomb's law. Making a charge move or "disappear" violates Electrostatics. (This is the same reason that Coulomb's law does not hold to find the force between two moving charges.)
To truly understand the force experienced on one charge due to another, you need to find the field of the second at the location of the first and use the Lorentz Force Law: $$F = q \left(\mathbf{E} + \mathbf{v}\times\mathbf{B}\right),$$
and to find the fields $\mathbf{E}$ and $\mathbf{B}$, you need to use Maxwell's Equations:
\begin{equation} \begin{aligned} \nabla \cdot \mathbf{E} &= \frac{\rho}{\epsilon_0}\\ \nabla \times \mathbf{E} &= -\frac{\partial \mathbf{B}}{\partial t}\\ \nabla \cdot \mathbf{B} &= 0\\ \nabla \times \mathbf{B} &= \mu_0 \mathbf{j} + \frac{1}{c^2}\frac{\partial \mathbf{E}}{\partial t} \end{aligned} \end{equation}
These equations tell us that disturbances in the field propagate at a speed $c$. So in other words, if charge $A$ was disturbed at a point, then the information that it has been moved will not reach charge $B$ instantaneously, but will travel at a speed $c$ from $A$ to $B$. (As should be expected, since in some sense special relativity and the constancy of the speed of light arose as a "consequence" of Electromagnetism!)
Here's another way to show that it can't be an "action at a distance" force, if you accept special relativity. Consider two inertial frames $S$ and $S'$, with $S'$ moving with respect to $S$ at a speed $v$.
Suppose in $S$ you moved charge $A$ and charge $B$ sensed its removal instantaneously. These two events would then be simultaneous, i.e. the time interval between them would be $\Delta t = 0$. However, from the relativity of simultaneity, we know that two events cannot be simultaneous in all inertial frames, and therefore in $S'$ there would be a time interval between $A$ moving to a new location and $B$ sensing it. However, this would mean that for some time interval $\Delta t'$ (according to the observer in $S'$), there was a force on charge $B$ that had no "source". But this violates the very idea of an inertial frame! And so we have a contradiction.
Thus, if we want special relativity to be true, we cannot have instantaneous forces, and this includes Coulomb's law.
We generally imagine or define Coulomb's force to be "the force experienced by a charge due to the presence of another charge in the space(simple explanation)" but in a broader sense we should state it like "the force experienced by a charge due to the presence of an already existing so-called 'Electricstatic field' which was produced by another charge which was in 'static' condition for sufficiently long time". You will clearly understand why this is significant as you go through the following:-
This is in accordance with the special theory of relativity (Einstein hits it again) which claims that no information in the universe can travel faster than light.
Now as you are concerned with proton and electron in an atom, if the proton suddenly disappears, the electron will not experience its absence instantaneously as the disturbance will move at a speed 'c'(as the disturbance propagates as an EM wave and EM waves propagate at the speed of the light).
But when we are talking of very small distances the effect is not dramatic. Imagine you are rotating a ball attached to a string of small length, then as soon as the string breaks, it immediately goes tangentially. So a layman can't say that there was a time lag between the breaking of string and disappearance of 'centripetal force' on the ball. Similarly, as you are talking at the atomic level the effect is not at all dramatic but yes, it is still there.
But imagine huge distances like in terms of light years. In that case the effects will be very dramatic. If a charge is displaced from the original position or disappears, another charge situated light years apart will not feel the change instantaneously( In fact, it will take years, at least more than what light would take to travel between those two charges). So at any instant during that time each of the charges would feel different forces.
Does that mean Newton's third law is not conserved and ultimately is the linear momentum not conserved?
Now think, initially when there existed only electrostatic field, there was no momentum density in the field(but it still had energy). But as soon as the charge is displaced or disappears, the electric field is no more 'static', it has changed, so it will store some momentum or it will have some momentum density. Now if you add all the mometums , of the charges as well as the field, you will come to a conclusion that the momentum is still conserved.(this is an extra note to see the beauty of Physics though you had not asked about it originally).