If you can run an ethernet cable to the Arduino, why can't you run power? An Arduino with ethernet shield on batteries does not make sense.
I second this, and would add that PoE makes a lot of sense for this purpose. You don't even have to implement 802.3af, you can just split off one of the unused pairs in your ethernet cable at both ends and use that pair to carry DC power. I'm currently doing just that for one project and I can testify that it works wonderfully.
Actually you guys are completely right about the Ethernet shield: if there is a cable there is power (or PoE). Still the scenario with the WiFi module (I have the Roving Networks RN XV that I can put on/off with a transistor) makes sense. Or I'm thinking about working with a 2.4Ghz wireless module ...
Anyway, thanks for your insights!