Graynomad:
Honestly this seems like a lot of circuitry to solve a simple problem, why not use an external series regulator or a $12 switching module.
I'm not sure what kind of switching module you are referring to, but if you mean something like a LM2576, I would still need an inductor, a cap and some resistors, pretty much the same as I have now.
cr0sh:
[...]
Why not just set up a cascade of linear regulators on heatsinks, then tap those for what you need - battery to LM7812 to 7805 to Arduino (bypassing the Arduino's 7805, of course)? That, or the switching supply would probably be the better options.
I don't like the fact that linear regulators are eating all the excess voltage, I don't want to waste power as this is a battery driven setup 
( Even though I think it could suffice for this project )
SirNickity:
This guy has a nice discrete circuit for dropping some voltage in preparation for a linear regulator's comfortable input range:
[...]
This is basically a linear regulator, the transistors will eat the excess voltage.
iyahdub:
Isnt that like trying to hang a picture with cement ?! Simplest solution is just the voltage regulators- They so simple, and will allow you to expand at a later stage if needed without much hassle !
Or am i missing the point here ?!?
Then again, when all u have is a hammer, everything starts to look like a nail !!
Well, the simplest solution is indeed a voltage regulator
but again, I want to take into account efficiency.
It may be a crazy idea to begin with, but experience tells me you can learn a lot by thinking outside the box, even if you find yourself choosing the safe/well-known solution in the end 