What confuses me is, the load cell needs 5v, but the sense voltages are just under half the input voltage, so really
It would be helpful if you could post the spec sheet for the load cell. Since load cells are basically varistors, I would be surprised if the voltage you're referring to is not the maximum allowable voltage that doesn't cause excessive self-heating. If you look at
this link from TI, they are quite explicit re: the need of your ADC reference voltage and the load cell input voltage to be the same. By using the same reference voltage, any disturbance on the voltage supply side is referenced and hopefully canceled out by affecting the reference voltage input and the ADC input equally (on a ratiometric basis).
So, if you are using a Teensy 3.1, I would address the low differential voltage difference of the load cell by enabling the Programmable Gain Amplifier (PGA).
Pedro's library allows a gain of up to 64x, IIRC. Not sure how the PGA works though, so read up on it too. At the very least, with a gain of 2x, the PGA will double the output voltage of your load cell, bringing its output range back into the same range as the Reference voltage input (AREF). So I'd consider using a 2.5V zener diode (GND to AREF) to produce a stable AREF power supply, then run the AREF voltage into the top of the load cell, then use the PGA to bring the input signals up. Adds perhaps a bit of noise (PGA) but likely eliminates a lot of noise and drift.
Having a separate reference voltage for the bridge and the ADC input is IMO a recipe for disaster. Don't do it. For example, if the thermal drift characteristics of your voltage regulators vary (and they more than likely will), then the voltages can drift at varying rates as a function of ambient thermal conditions. You'll pull your hair out in frustration, as calibrating that will result in a rig that will only will work at one temperature. OK for some applications, but really bad design practice, IMO. Of course you could throw lots of bucks at the problem by buying precision references that have very low thermal drift characteristics, but you'd essentially be throwing money at a problem that shouldn't exist in the first place.
If you end up needing something more accurate and capable of handling temperature-induced drift better than the cheap zener diodes I referenced above, consider a shunt-style reference as an alternative for out-of-box Teensy compatibility.
Digikey is carrying a number of them. For through-hole shunt references with accuracy of 1% and up,
see this list. Even a 0.1% reference can be had for less than $2 in single quantities. I doubt you need something that accurate as long as AREF=V
in for the load cell, but it's available.
Also, if you want to use a series reference instead of a shunt-style reference, you need to remove the 470 Ohm resistor from the Teensy board that ties AREF to 3.3V.