Another thing about regulators: Even the most efficient regulators are not 100% efficient. Linear regulators are far, far from efficient. So, if you're dropping 4v from a 9v to reach 5v, that's 4v that's just heating the air around your regulator. This pretty much scraps any advantage from trying to conserve power through sleep modes. Running it direct from batteries removes this waste.
The ATmegas are rated to 5.5v, so while four alkalines might be pushing it (don't fresh ones start around 1.45 or so? I don't know), NiMH would likely be just fine. Remember, 5.5v is the serving suggestion. The actual capabilities of the chip could be well beyond that. (You take a risk if you overvolt it, but if it's worth the $4 to you to try it and see what happens, by all means.. give it a shot.)
Fuses aren't bad. Don't be intimidated, just devote an afternoon to reading up on them. There are online calculators that let you pick your options and it'll spit out the values. Then, you follow a tutorial on using avrdude from the command line -- which also isn't a big deal. You can just about copy the command line used by the IDE.
The BoD would be worth it, in my opinion. I would rather have a clear indication when the batteries need to be swapped than slowly having performance turn to crap. Ultimately, it's your call, just don't let having to set fuses scare you off. It's not hard.