Firstly, although probably obvious, you have forgotten to mention the key feature in the Comlomb force, which I think is key in 'explaining' Newton's third law - that the forces felt by two charges, $q1$ and $q2$, are equal and opposite, since the force is proportional to both $q1$ and $q2$.
You have tried to understand this from a classical viewpoint, which appears to make sense. I will try to address your first question in a classical setting. As far as I can see, the action-reaction law could still exist if there wasn't a Coulombic force. To see this, consider a force that is repulsive on short distances - although seemingly contrived, it would be sufficient to form a microscopic understanding of Newton's third law. This does not require the existence of charges whatsoever.
garyp pointed out that Newton's third law is also applicable in gravity. This is certainly true in Newtonian gravity. In fact, we can also regard Newtonian gravity as a 'Coulomb-like' interaction, with charges replaced by masses (and obviously only attractive). In relativity, however, it is no longer obvious what place Newton's third law would take in the theory.
A full microscopic explanation of Newton's third law, especially more fundamentally "why don't we fall through the ground" or "punch through a wall" (which might seem possible if we are just thinking of microscopic things classically, since much of the atom is empty space!), relies on quantum mechanics, e.g. the Pauli Exclusion Principle. However, your classical understanding is a good one to have, but it must be remembered that classical descriptions tend to break down when you take them too far.
(Edit: I will incorporate the idea of symmetry into this answer after some fruitful discussions with SaudiBombsYemen, which motivated me to think about this topic more deeply.
While Newton's laws hold in any inertial frame, with or without symmetry, there is a close relationship between Newton's laws and symmetries, namely that Newton's laws assert that momentum is conserved in an isolated system, while translational symmetry implies conservation of momentum. This means that, with translational symmetry, Noether's theorem does indeed imply Newton's laws, or at least the momentum aspects of Newton's laws.
However, it is easy to come up with an example that does not have translational symmetry, but Newton's laws, in particular, the third law, still applies. For instance, a particle sitting still in a bowl. Obviously, this system has no translational symmetry, so Noether's theorem does not apply; however, we can apply Newton's third law on the balance between gravity and normal reaction forces (which are a manifestation of the electrostatic repulsion discussed earlier)
Another seemingly contradictory situation that one might think of is: Why do we observe Newton's third law when two particles collide, even if the background is not translationally symmetric? This is because we take the process of collision to be instantaneous, and in such a small (pointlike!) region of space, we would have translational symmetry, and hence conservation of momentum. Note, however, that this conservation of momentum is not the same as conservation of momentum of the whole system.
Credits to SaudiBombsYemen for much of this content.