This quote from the wikipedia article on History of Chemistry might provide some insight into the determination of atomic mass:
Chemists in different countries developed several different incompatible atomistic systems. A paper that suggested a way out of this difficult situation was published as early as 1811 by the Italian physicist Amedeo Avogadro (1776-1856), who hypothesized that equal volumes of gases at the same temperature and pressure contain equal numbers of molecules, from which it followed that relative molecular weights of any two gases are the same as the ratio of the densities of the two gases under the same conditions of temperature and pressure.
So this implies that you could take equal volumes of different gases at the same temperature and pressure, then weigh them and take the ratios. This would allow you to get relative masses for $\ce{H2}$, $\ce{N2}$, $\ce{O2}$, $\ce{Cl2}$, $\ce{Br2}$, $\ce{I2}$. Other gases could be used, but they wouldn't be as useful here. You could then determine that $\ce{H2}$ is the lightest gas, and that $\ce{O2}$ is 16 times heavier, $\ce{N2}$ is 14 times heavier, and so on. You don't even need to know that these are diatomic gases in order to make these measurements. Once you had these determined you could move on to gases like $\ce{CO2}$, or $\ce{H2S}$. Once you knew the mass of the gas molecule and what elements were in it, you could calculate how much of each element must be there, and by subtracting the mass of the known element, the remaining mass must be the atomic mass for the other element. As you accumulated more data you could approach substances that don't easily form gases, such as $\ce{NaCl}$. If you know the mass for $\ce{Cl}$ you could determine the mass for $\ce{Na}$.
What I suggest might not be the way atomic masses were determined, but it would probably work. Looking at this image of Mendeleev's original table shows they already had pretty good estimates of atomic mass by 1869.