The modern low voltage versions of a bare ATmega chip can run from either 2xAA or a lithium coin cell - you wouldn't want to use a voltage regulator, as that is not only unnecessary but introduces losses but increases the required input voltage by its
dropout meaning your circuit will fail earlier in the discharge curve that in it would without.
Bypassing the regulator on an Arduino Mini style of board is possible. You probably do not want a board with an on-board USB-serial solution.
You'll need to make sure the clock rate is low enough for operation at the rated voltage (and for sleep efficiency). This might involve using the fuse for the internal oscillator and ignoring a crystal/resonator that might be present, though if your board was originally intended for 3.3v operation it might be okay.
You will also need to set the brownout detector to the lowest voltage or disable it entirely - this again is in the fuses.
A boost converter to a higher voltage is possible but may not be a good idea, especially from a coin cell. This is because to supply 1 milliamp at 5v, a boost converter must draw 2 milliamps at 2.5v - and then a bit more, to account for its own losses. If you go shopping for a boost converter to use, make sure it has an enable, look at the quiescent power consumption when disabled and enabled without load, and look at the minimum input voltage.