Can batteries be damaged?
1) Do batteries such as CR123As and Eneloops have built in discharge protection so that they stop supplying power when the voltage is too low?


No, they don't.  They just run till there is nothing left.


  2) If no, will draining a non-rechargable CR123A be dangerous or problematic in any way? And will draining MiMHs down to 0.85v/0.55v hurt the batteries?


A single cell can be run completely flat without problems. NiMH may need some "recovery" to wake them back up again, but shouldn't suffer serious problems (and no safety issues).  However, batteries are a different matter: see below.


  3) And, a question that I suppose applies to any battery powered Arduino project: When the supplied voltage drops below the Pro Minis BOD limit, will the Arduino stop using any power, or will it continue draining the batteries until they are completely empty? (In the first case I guess I could stick with the factory set BOD at 2.7v to protect the batteries.)


It will continue draining power. The BOD is a reset circuit - designed to recover the system into a known good state after a dip in the power. A permanent decrease in the input power is beyond the scope of the BOD system.  It will just get stuck in a BOD reset loop and consume all your remaining power.


  4) Finally, relating to the first question: Should I try to construct some kind of battery protection in the circuit, or is unnecessary when using CR123A and NiMH batteries?


For a single non-rechargeable cell you can just let it run flat. For NiMH you need to protect them.  Here's why (and what I was alluding to above):



When you have two or more cells in series (a battery) the current flows through all the cells of the battery equally. That is all fine when the cells are all fully charged - however no two cells are precisely the same. 

As the battery runs down each cell will approach "empty" at a different time. With a single cell that's not really a problem, since it will just stop providing enough current to run.  However, with multiple cells one cell will run flat before the others. At that point the current provided by the other cells which still have some charge in them will be pushed through the flat cell backwards.  It is at that point that the flat cell becomes irrevocably damaged.  Current flowing backwards through the cell will try to reverse charge the battery and mess up the internal chemistry beyond recovery. 

In the best case scenario, your battery will now have a much lower capacity and need recharging far more often. Worst case scenario: that damaged cell overheats and explodes. 

The most prevalent problem that is caused by reverse charging is the depositing of metal crystals on the dielectric (the separator between the two electrodes) in the cell which grow and pierce the dielectric causing short circuits within the cell. There is no way back from that happening.

So you should protect your NiMH batteries from over-discharge by cutting the power to your circuit when the voltage drops below a specific threshold.  You should also recharge all the cells individually, not together in series, or they will end up unbalanced and the same problems of over-discharge can occur.



As a side note: I use the terms "cell" and "battery" with their "proper" usage: A cell is a single power-producing unit, such as an AA "battery".  A battery is a collection of cells.  This is the proper usage of the words, not the common usage where battery can also be taken to mean cell.  I use these terms specifically to differentiate between a single unit and a collection of units because of the major differences in how you need to handle them. It helps prevent confusion if you know that I am talking about just one AA (a cell) or a collection of three AA in series (a battery), for example.