Design Questions for a Nixie Tube Clock
I was thinking about a Atmega328P with the Arduino bootloader already on the chip but that may be overkill for my project.


An ATmega328P is a good choice, as there is a free software toolchain as well as the Arduino IDE if you are more comfortable with that, and programmers are cheap (~$15). Additionally, there is a lot of community support and it is very easy to get an ATmega up and running on a board by itself. Take a look at the Arduino UNO schematic, and strip out the things you don't need. Basically, at a bare minimum, it boils down to the following:


A stable logic voltage supply (5V or 3V3 would be a good choice).
A way to program the device. Easiest way to do this is with an ICSP header (6 pins, programmers are cheap, very easy to use).


A crystal is optional. The ATmega328 has an internal oscillator. Because you don't need a high clock frequency, and I presume you'll be using an external RTC, you don't need a stable or fast clock.

You'll need to choose the peripherals for your clock: I'm guessing you'll want an RTC and some I/O expanders (or shift registers) to drive the clock.




  make sure the chip doesn't lose the program every time I disconnect power.


Every microcontroller (within reason) has non-volatile (flash-based) program storage and will retain its program code through power cycles.



Other reasonable microcontroller alternatives:


If you need less horsepower, an ATtiny would be a reasonable choice. However, most ATtiny's will also have less I/O, which might be an issue. The toolchain/programmer is the same though.
If you want a more modern/capable/fast MCU, look at ARM Cortex M0+ and M4 chips. I would recommend STMicro or perhaps Freescale (now NXP) Kinetis chips. Keep in mind that STMicro programmers are much cheaper than Freescale programmers.