First, Hubble and his collaborators were measuring the velocities of galaxies, each made up of about a billion stars or more. Their measurements did not distinguish between the cosmological redshift and the redshift due to 'peculiar velocity', that is the motions of the stars not due to expansion. They were fortunate, however, that the expansion of the Universe is fast enough that the cosmological redshift is much larger than the peculiar redshift for most galaxies which they could measure at the time. The typical spread of velocities of stars within the galaxies they were looking at are $100-300\,{\rm km}\,{\rm s}^{-1}$, this mainly contributes to a broadening of the spectral lines of the galaxy as the lines of many individual stars with slightly different velocities overlap. The galaxies themselves can have peculiar velocities of a few hundred ${\rm km}\,{\rm s}^{-1}$, or slightly more for those in galaxy clusters, up to $2000\,{\rm km}\,{\rm s}^{-1}$ or so in the most extreme cases.
The velocities on Hubble's original distance-velocity diagram are up to about $1000\,{\rm km}\,{\rm s}^{-1}$, and have a reasonably clear trend with distance. The limiting factor in the maximum velocity shown on the plot was actually not the velocities, but the distances; they had already measured velocities of almost $4000\,{\rm km}\,{\rm s}^{-1}$. They suspected these high velocity galaxies were further away based on their sizes and luminosities, but had no means at the time of making more accurate distance measurements for these objects. If you read the original papers, the tone is pretty tentative - it was clear that it would be pretty strange for galaxies to happen to be receding from us in all directions by chance, and the possibility of a link to "de Sitter's theory" was clear, but they cautioned that they felt more measurements were needed to solidify the result. To sum it up, they suspected that what they were seeing was due to cosmological expansion, and that this was the dominant component of their measured velocities, i.e. the peculiar velocities are "negligible", to speak loosely.
You're right that to measure the redshift, you first need to know the intrinsic wavelength of the spectral line in question. The original papers are surprisingly a bit vague about the specific lines used, saying only that they were stellar absorption lines and that they used more than one per galaxy. Measurements of velocities from lines were fairly routine by this time, so I guess they didn't feel a need to elaborate on all the details; the distance measurements being the more cutting edge part of the work, they elaborate much more on these. Presumably they would be using the strongest lines, at a guess maybe Calcium, Sodium or Magnesium lines. People had already worked out from the solar spectrum and spectra of stars in our galaxy which lines were typical for stars, and since galaxies are made of stars they were expected to have more or less the same spectral features. Given 2-3 lines that are expected to be among a small handful of typical strong lines, it's not too hard to identify them based on the relative wavelengths, their rest wavelengths then being known from arc lamp measurements in the lab.
References for the above are the original paper by Hubble and a related paper by Humason, who did many of the spectral measurements.
