Power consumption can be done mainly by changing to an barebone Arduino setup, think the most cited article about this is http://gammon.com.au/power .
The initial outcome is that, to save power, forget about using a development board. Further savings (like reducing clock speed) would be overshadowed by the huge overhead of the voltage regulator and USB interface chip.
I think Lars used as OpAmp an INA333 as linked in an older posting above: http://bildr.no/view/1409684 and no additional ADC so there is really an option for better reading than 0.1 kg resolution.
I see this two options: Use an additional ADC plus OpAmp / PGA or a chip who has both integrated, see my posting under http://forum.arduino.cc/index.php?topic=198139.0 - so you see, you are not alone. 
you may also have a look at the Seeeduino Stalker who has a lot of build in (charger circuit, RTC, SD) http://www.seeedstudio.com/wiki/Seeeduino_Stalker_v2.3