How do we determine that an object is neutral? 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.
 A: Okay, lets imagine I'm in a room full of balls with random charges and masses. Can I determine which of the objects are positive, negative or neutral? Thats the essence of your question, if I understand you correctly. 
The answer is yes.
I just grab two random objects. If they attract I don't know whether it is due to gravitational or electric attraction. In that case I just continue to grab other objects until I find a pair which repels. They are obviously both charged, since gravity can only attract. I call that charge positive. If I continue to hold other objects near my two positive charges I can identify more objects which repel. I add all of these charges to the group of positive charges. A positive charge doesn't nececcarily repel from every other positive charge, because for some objects gravity might be stronger than the electric repulsion. But it is enough if I can can find any positive charge within my group wich repels my object to add it to the group of positive charges.
In the same way I can identify a second group of charges which mutually repel each other, however they always attract with every object in the first group of positive charges. So they are different and I call them negative charges. I have now two groups of objects, within each group I can find for every object one other object such that they repel each other. But positive charges and negative charges (two objects from different groups) always attract each other. 
Now I can grab one positive charge and one negative charge (preferably the ones with the biggest repulsion, that is the biggest charge). If I find an object which isn't repelled by both the positive and negative charge, it doesn't belong to either of the two groups and I call that object neutral.
You might say that maybe the object is just slightly positively charged, but the gravitational attraction with my other positive charge is stronger then the repulsion and they still attract. However if you compare it with all other positive charges we have found, that would become more and more unlikely, because the object would need to have a mass so big that the gravitational attraction overrides even the repulsion to an object with arbitrarily low mass but arbitrarily high positive charge.
Note that I didn't even need to assume equivalence of gravitational and inertial mass, the procedure will work fine even if the are not equal.
A: Find a set of equal-mass objects that all mutual repel. How do you confirm that they are equal in mass? Attach springs to them and have them oscillate horizontally. Objects of equal mass will oscillate at the same frequency. Horizontal motion negates the effect of Earth's gravity and electric charge.
Create a second group of objects that (1) each have the same mass as the objects in the first set, (2) mutually repel, and (3) attract the objects in the first set. Requirements (1) and (2) are satisfied by repeating the same procedure in the first paragraph. Requirement (3) requires an extra step of testing that an object that is to go into the second set attracts objects in the first set.
Now, choose a pair of objects--one from set 1, one from set 2--that have the greatest attraction to each other. This can be done by fixing one object in place and attaching the other to a spring so that it extends horizontally. Choose the pair of objects that causes the maximum extension in the spring.
Since all of the objects are the same mass, they will all attract each other with equal gravitational force. So, if one pair of objects attracts each other with a greater force than another pair, that first pair must have a larger quantity of charge.
Now, to find a neutrally charged object, fix the location of the two objects found in the previous paragraph. Place the object to test midway between them. The gravitational force of the two objects cancel out, leaving only the electric field between them. If the object being tested is electrically neutral, it will remain motionless. Otherwise, it will move towards one of the charged objects. The mass of the test object does not matter.
