Use offboard switching regulator to make 5V for the Uno vs knocking 12v down to 5v with the onboard heat dissipating regulator.
Run the Uno slower 8 MHz, 4 MHz - see the clock portion of the datasheet.
What is the base power draw with nothing attached with an empty sketch?
Oh around 40mA or so is a good guess. As others have said it's not a good board for trying for minimum current consumption what with the power on led, usb serial convertor chip, voltage regulator consumption, etc.
Oh... If the base is around 40 mA that really gets me out of this problem, though I have to keep everything on. I only have a ~5 mA chip, a small LED and a motor shield (where the motor itself is externally powered). For some reason I was thinking 250 mA, I'm not sure where I got this from. I had 500 mA to work with and a linear actuator taking 300 mA and possibly a second Arduino. That seems quite possible now.