I think I would use 2 switching regulators like this
and adjust to what ever levels you wanted.
Bring the Arduino 5V in thru the USB connector, other threads have suggested the voltage regulator used in recent arduino's does not handle being bypassed well and it can be damaged.