There are many solutions for 5V output. USB can typically take at least 5.25V, which means that 5.3V is pushing it perhaps too far for some very sensitive devices.
However, you don't need a 7805 for getting to 5V stable. There are many LDO regulators with 0.5A - 1.5A current ability that have much lower drop-out. A LF50AB for example can go from 5.3V to 5.0V up to 500 mA (which is the max draw on a standard USB 2.0 port.)
Another option is, as has been suggested, a switching converter of some sort. These are more efficient than linear regulators in many cases, although when going from 5.3V to 5.0V with a linear regulator, you're already a 94% efficiency, which is great in that case. A particular regulator I like because it's cheap and reasonably high current and efficiency is the Murata OKI 78SR. It takes 7-35 Volts in, and outputs 5.0V up to 1.5A, with the same pinout as a 7805, but uniformly high efficiency.
Finally, batteries are typically higher voltage than indicated when fresh, and lower voltage than indicated when depleted. Thus, using linear regulators is often not the right choice. Putting all the batteries in series and using a switching buck regulator (as suggested above) is a good way to get around this. Putting all the batteries parallel and using a boost converter is also often acceptable -- and for Lithium chemistries, easier to charge correctly. If your batteries start above the target voltage and end below the target voltage, you will need a buck/boost, SEPIC, or similar converter that can work with the input being both above, and below, the input voltage. Pololu has some ready-made ones, although they are not terribly high-current rated, and these topologies are often less efficient than buck-only or boost-only.
Holding the MCU in reset is both a decent way to reduce its current consumption to almost nothing as well as indicate that the battery is low. Unfortunately most ATtinys have 2.7V as their closest BOR value so you will require an external voltage monitor if that is not high enough for your purposes.
Best Answer
The safe voltage range for the ATtiny45 is between 2.7V and 5.5V, so you should be able to connect the battery directly to the MCU provided you don't need a different specific voltage for external components.
A switching power supply could allow you to get longer life out of the battery if you run it at about 3V or so the whole time, both because the MCU will use less current at the lower voltage and because the reduction of output voltage with a switching regulator translates to a reduction of input current (after taking the regulator efficiency into account).