How do Temperature Scales work? How exactly do temperature scales work?
If my understanding is correct, the Celsius scale has two fixed points: (definitions of temperature irrespective of scale)
 1. The freezing point of pure water at 1atm (labelled 0 C)
 2. The boiling point of pure water at 1atm (labelled 100 C)
Note that 0 and 100 are completely random numbers.
All other values of temperature are only defined using distance on a thermometer.
eg. 50 deg. C is exactly half-way between the marks of 0 and 100 on a thermometer. It 
doesn't necessarily have to be "half as hot" as 100 deg. C (what is half as hot anyway?)
Since the coefficient of expansion depends on temperature anyway, how do we justify these scales?
The Kelvin Scale is simply C-273.15, to ensure that all temperatures remain positive. 
So, how does the RMS speed of gas molecules (which is independent of human-invented temperature scales) depend so 'cleanly' on our arbitrary temperature scales?
 A: Celsius was defined by fixing the mercury's expansion coefficient with respect to temperature as constant. It is now defined as Kelvin plus 273.15, not the other way around. In fact, the freezing point of water under standard atmospheric temperature is 0.000089(10)°C, boiling point 99.9839°C. Mercury thermometer is now an approximate measuring device, as any measuring device, rather than the definition of Celsius scale.
The original definition of Celsius and Fahrenheit are arbitrary and artificial, but Kelvin, or thermodynamic temperature, is based on universal physical principle, i.e., second law of thermodynamics. This relation with fundamental physical principle makes Kelvin the "clean" scale of temperature. 
Kelvin still depends on water, with its triple point fixed at 0.01°C (273.16K). The proposed redefinition of Kelvin will fix Boltzmann constant, the constant relating temperature and energy. That will make Kelvin even more natural.
A: Your confusion was one of the things sorted out by thermodynamics. The definition of temperature is via the entropy relation:
$$ dS = {dQ\over T} $$
Not in terms of thermal expansion of anything, so that in principle you can figure out where 50 degrees is in a celsius scale by doing the following:
make an object at Celsius 0 degrees and at Celsius 100 degrees, and run a perfect heat engine between these, using a Carnot cycle. This cycle will produce work from heat with an efficiency:
$$ {100 \over T_1 } $$
Where $T_1$ turns out to be 273 Celsius units, so you can convert from Celsius to Kelvin using this idealized definition.
Then you find the point T at which a perfect heat engine between temperature 0 and temperature T runs at efficiency
$$ 50 \over T_1 $$
and this T is 50 celsius. It isn't exactly the same point as halfway on the thermometer between 0 and 100, but it's close.
The entropy of an ideal gas is simple to calculate, and for an ideal gas
$$ PV=nRT$$
So in practice, to determine absolute temperature, you use a gas thermometer. The product of pressure and volume is the absolute temperature, and you can make the pressure arbitrarily small and therefore reach the ideal gas limit as precisely as you like.
Carnot's work was important because it settled this question of defining a temperature scale independent of the arbitrariness of thermal expansion coefficients, and showed that it was equivalent to the gas thermometer scale, which was widely used in the early 19th century anyway, because people suspected correctly that it was more universal than a water or mercury scale, since different gasses had the same law.
A: The short answer is that only absolute scales--those with their zero at zero-energy-per-particle--like Kelvin agree with the energy.
In short, the reason for the Kelvin on Rankine is not "to ensure that all temperatures remain positive", but to make temperature and mean energy isomorphic.

I see that I failed to address one of your points:

Since the coefficient of expansion depends on temperature anyway, how do we justify these scales?

Most coefficients of thermal expansion vary gently over human temperature scales, so we can use most materials and get reasonably linear instruments. This just represents the non-linear terms being small and the range of temperature regularly used by humans (say between 250--450 kelvin) representing only about a factor of two in mean energy. 

So, how does the RMS speed of gas molecules (which is independent of human-invented temperature scales) depend so 'cleanly' on our arbitrary temperature scales?

In actual fact it is the other way round. The energy per particle is a much more fundamental concept than "the volume of some sample of mercury" or "the length of a copper rod" The right question is why are out instruments so linear in energy?
