A lot of questions here.
Is there any reason not to use an Arduino Mega
No
Do Arduinos have circuit breakers /resettable fuse built in? Or is it a good idea to put one into the 12VDC line?
No and No. They are a waste of time in a control application like this because they don't trip fast enough to protect anything.
battery that trickle charges and only comes on if the 12V supply fails
You need a diode to stop the battery discharging into the failed power supply.
probably a bunch of SSRs
Yes sounds like a good option, I would also budget for some mains filters to stop switch on interference crashing your arduino.
the rest is a matter of personal choice.