This has been bothering me for a while. Imagine that you are an experimentalist who does not have any known mass or charge to compare against. Imagine also that you do not have any idea about the relative distribution of positive and negative charges around you.
You are aware of the laws for Newtonian gravitation, electrostatic Coulomb force and the Newton laws of motion. You have settled on a choice of units by fixing the value of $G$ and $k$ (the gravitational constant and the Coulomb constant). I will assume we already know the equivalence between gravitational and inertial mass, otherwise the problem is more complicated. I will also ignore nuclear forces and quantum effects, which only make things more complicated, and were not part of the knowledge of the people who did the initial measurements of charges and masses.
You are able to perform kinematic experiments where you take a system of particles and you measure their trajectories over time in a fixed inertial reference frame.
If you can find an object that is neutrally charged (denote its mass by $M$), then you can determine all other masses and charges systematically using this object as a starting point by the following procedure:
Find a charged object. This requires some luck to find it initially, but you can be certain that an object is charged if you observe repulsion between this object and another object (the converse is false, attraction can be due to a combination of gravity and electrical forces). Since gravitational interactions are purely attractive, this implies the presence of charge. Now find an identical object of this type (it is not completely obvious how to do this, but we could assume that we have some repeatable procedure to find the same kind of object). The point is to know that their masses and charges are identical. Denote the masses and charges of these objects by $M'$ and $Q'$.
Since we have a neutral object, we know that the interactions between this object and the other two are entirely due to gravity, so the charges of the other objects do not play a role when they interact with the neutral object. Observe the two-body motion between the neutral object and one of the charged objects. By Newton's laws we find $M\ddot{\mathbf{x}} = -\frac{GMM'}{|\mathbf{x}-\mathbf{x}'|^3}(\mathbf{x}-\mathbf{x}')$. So by measuring the trajectories over time, we can find $M'$. Similarly we can find $M$.
Now we take the two identical charged objects. We do not know $Q'$ yet. The equations of motion are given by $M'\ddot{\mathbf{x}}_1 = \frac{kQ'^2 - GM'^2}{|\mathbf{x}_1-\mathbf{x}_2|^3}(\mathbf{x}_1-\mathbf{x}_2)$. This allows us to determine $\alpha = \frac{kQ'^2 - GM'^2}{M'}$. Since we already know $M'$, we can solve for $Q'$ as $Q' = \pm\sqrt{\frac{\alpha M' + GM'^2}{k}}$. The choice of sign is arbitrary. We will decide that the object is positively charged, giving us a unique value for $Q'$.
We can now measure the charge and mass of every other object by observing its interactions with either the neutral object, or the charged object. The interaction with the neutral objects allows determination of the mass just as in step 2, and the interaction with the charged object allows determination of charge once the mass is known.
So the entire procedure for determining masses and charges relies fundamentally on the choice of a neutral object. But how do we find this object initially?
Here are a few ideas that do not really work:
Take a large number of particles together and hope that the charges cancel out on average. This relies on an additional assumption that positive and negative charges are distributed somewhat uniformly. But this is not clear without having done any measurements. Statistical arguments based on entropy do not work because there are interactions between the particles which makes the problem different from one about diffusion in ideal gasses.
Since large collections of identical charged objects ought to be unstable, a large ball of uniform material should be approximately neutral. This comes from the usual belief that the dominant interaction is the electrostatic force, while gravity is negligible. If that is true, then you need negative charge to attract the positive charges, and the object is stable once the charges cancel out. The problem with this is that it is possible to keep a large collection of positive charges together by gravity instead. Without having done any measurements, we cannot know which force is dominant yet (remember that we are doing this prior to the measurement of any charges and masses!). Instability implies the presence of charge, but the converse is false, as I already mentioned in step 1.
Consider the Earth, or some large conducting object, as neutral. This is just a special case of the first two methods, so it fails for the same reasons.
Take a conductive object which might be charged, and connect it to a conductor that is much larger than the object. The charges will distribute uniformly across the surface of the two conductors, and due to the surface-ratios, the small object should have a much smaller part of the total charge. The problem here is again the assumption that the large conductor is neutral (or at least, not very charged), so it fails for the same reason as the previous method (the small object could have a small part of a very large charge!).
Take a large conductive box that acts as a Faraday cage. Place a test object inside the box, and bring a second object close to the box, but outside. Compare the forces on the two objects to the forces obtained after taking out the box. If there was any difference in the measurements, the objects must be charged, because the metal box can shield the electric fields between the objects, but not their gravitational fields. The problem with this method is that we have introduced a new object that has its own interaction with the two objects. It becomes a lot more complicated to solve for all masses and charges, and we have to treat it as a special case of the first method I describe in the next section.
Here are a few ideas that might work, but have some drawbacks:
Choose a sufficiently large system of objects and perform kinematic measurements to measure the interaction constants $\alpha_{ij}$ between every pair of objects. This idea is discussed further in my other question. As mentioned there, we run into technical difficulties trying to solve a large system of polynomial equations in many variables. This has the computational problem of finding a solution, and another problem of proving that the solution is unique. The procedure I described in the current question is a special case where we already found a neutral object. In this case solving the equations is much easier because the masses can be uncoupled from the charges.
Take into account the magnetic interaction between charged objects. The Lorentz force law relates the force on a moving charge to its charge, velocity and the existing magnetic field. The magnetic field produced by the other moving charges is in turn determined by the Liénard-Wiechert formulas. This force is not of the inverse-square type that occurs in Coulomb's and Newton's force laws, so there are additional terms that depend only on the value of charge. This allows decoupling charge from mass once again, and we can then solve the system of equations in the previous method more easily. The problem with this method is that the magnetic force between two moving charges is on the order of $v/c$, so we need either very large velocities or very good precision on the instruments to measure this accurately.
Similarly, take into account other special-relativistic effects, and the wave nature of electromagnetic fields using Maxwell's equations and Lorentz force. This is the most complete model of classical electromagnetism, but it is also much more complicated, and requires a lot of precision to measure things.
I believe the last three suggestions are enough to determine charges and masses uniquely, but they are also fairly nontrivial. Moreover, I have never seen any discussion of such methods having been used by people prior to the 20th century, so I doubt that they were available at the time. Also the Lorentz force and Maxwell equations were likely developed after already having known sets of masses and charges to perform EM experiments. The experiments of Cavendish and Coulomb fit in the first category (the torsion balance is really a kinematic experiment that measures the interaction constant between the two masses). But they seem to have already made assumptions on the charge and masses of certain objects prior to the experiments, so there is a "turtles-all-the-way-down" problem in that there was always some prior knowledge on mass and/or charge assumed.
