First off, I would really avoid a 9V completely. They'll run down very quickly although they have the advantage of being small. Also since the voltage is so much greater you'll take a big hit in efficiency as well as idle current consumed by the regulator itself.

Next, a zener diode will give you a shunt regulator which is not what you want-- it's kind of like driving a car with the gas pedal floored and using your brakes to govern your speed. Lots of heat, and extremely inefficient since it acts as a short to bring to voltage down to the desired level. A linear regulator -your second option- is better but still not very efficient, and a "normal" version will drop about 2 volts across it, minimum.
You can buy "LDO" (Low Drop Out) regulators which will drop under a volt typically, but with the same mediocre efficiency. I don't have enough time (or patience ) to explain all this but Wikipedia has a dandy article on the ins and outs of linear voltage regulators: http://en.wikipedia.org/wiki/Linear_regulator

4 AAA (or AA) rechargeable batteries will give you roughly the right amount of voltage (5.3V), and if you use an ordinary diode in series that will go down to about 4.6V, which will be fine. No regulatory required and no current consumed when not plugged in. Should last a very long time.

Highly unlikely. Too little voltage will be ignored, but obviously I can't guaranty that or be responsible if it melts in your lap.

Larry