LiPo is MUCH easier to manage well than NimH.
Energy densities for top capacity NimH are about the same as LiPo nowadays.
(That was written in 2012. In 2021 LiPo energy densities are now typically somewhat higher).
NimH is a relatively hard battery chemistry to manage well. Charging at low rates is not usually advised and negative voltage deflection under charge or temperature rise are the usual end-of-charge detection methods. In contrast, LiPo is charged at constant-current until a set voltage is reached and then at constant-voltage until current falls to a preset level. LiPo will accept any lower-than-maximum rate of charge if desired, and can be recharged from any state-of-charge with no special conditions. (Handling very low voltage cells is slightly more complex, but all sensible charger ICs handle this - and very low voltage should never be allowed to happen.)
The ONLY reason I would think of using NimH in your context is safety - and if it was my son, I'd consider that I could make LiPo safe enough for him to use. LiPo can "melt down" very enthusiastically with flame, BUT it is extremely rare in practice and taking quite usual precautions should allow a safe result.
I would have no personal concerns over LiPo safety in a competently engineered system.
HOWEVER, NEVER use unprotected LiPo cells if you care about safety. The in-battery protection IC DOES NOT serve the same roles as the charger ICs do. The in-battery ones are just to stop people from doing stupidly dangerous things to the battery. That said, IF your charger is properly implemented, and if there is no chance of short or fire potential then most of the protection circuitry is not needed. I say "most" because, if there is e.g. a catastrophic equipment failure and e.g. a short circuit occurs, the in-cell circuitry will usually open-circuit the cell and prevent a fire.
Using the proper charger ICs should allow a very safe and reliable charger to be implemented.
You do not need gas gauging per se - just low voltage cut-out. If you can stop operation at say 3V / cell, that should be enough.
Protected cells should not cost vastly more. If they do, it MAY indicate that the cheap ones are bad ones. You can get utter junk LiIon batteries (and you'd hope to get a price advantage when buying junk :-) - if you were silly enough to buy them. There are enough reputable brand cells around that buying them probably does not cost vastly more. Ensuring that the cells are genuine is another matter. As a working position I suggest you start by assuming that anything bought from a low cost Chinese supplier is fake or out of spec and THEN try and prove otherwise. (NB: Racism? - definitely not!. It's based on experience - many visits to China and time in factories, etc. China is very, very large and has a vast range of sellers in a very competitive market place. In a casual sale, expect a certain portion of the sellers to be 'dodgy' at best.)
Added:
I was going to come back and mention LiFePO4 - AndreKr beat me to it.
Compared to LiPo, LiFePO4 (Lithium Ferro Phosphate) are safer, longer life and have lower energy density. You can buy RCR123A LiFePO4 batteries with 450 mAh x 3.2V capacity. (Some claim up to about 700 mAh but are suspect.) Tenergy LiFePO4 RC123A are widely advertised on ebay and should be good. Tenergy are AFAIK a "rebadger" BUT seem to sell good product. LiFePO4 MUST be charged properly, but are as easy as LiPo to manage. A very simple charger can be built using a constant-current regulator followed by a 3.6V constant-voltage regulator. This setup charges at constant current until Vlimit is reached, and then at constant V. Setting to 3.5V is better.
Here is a randomly found seller of Tenergy LiFePO4 RCR123A batteries. They also sell chargers.
NOTE:
Do NOT use Lithium Ion RC123 (3.6V nominal).
Do not use 3.0V Lithium Primary RC123.
The terms RC123, RC123A, RCR123, RCR123A etc are used somewhat interchangeably by sellers. Just be sure of what you are getting.
It sounds like you may have a handle on your question already, but I would like to add a couple of points about NIMH vs Alkaline.
You don't say how many watts or how many amps or milliamps your megaphone will be demanding, but the NiMH have a much lower internal resistance and so they can provide a much higher current without dropping their voltage as much as an Alkaline will. At higher loads, a Nimh will provide more power than a Alkaline; at very low loads, an Alkaline will provide more power (a very very loose generalization, but for example, an Alkaline will last forever in a remote control while the NiMH will not last as long - of course there is also the self discharge of many of the NiMH).
Also, most NiMH have a NOMINAL volatage of 1.2, but fully charged they start out at closer to 1.4 (I have measured some NiMH fully charged at 1.5) volts, and as mentioned already, hold to the 1.2 volts for most of their discharge.
The Alkalines often start closer to 1.6 volts, but quickly lose voltage as they discharge so that their average voltage through their life is about 1.2 Volts! Of course this depends on what the cut off voltage of your Megaphone is.
Don't forget that most NiMH have a very high self discharge rate and can lose 10-20% of their capacity in the first day, and 1% of their capacity per day just sitting there and are essentially completely discharged in 3 months or less! There are newer NiMH that hold 85% of their capacity over a year.
Check out http://batteryuniversity.com/learn/article/Nickel_based_batteries for more info.
As far as your 4 options, option 2 sounds like the best one. Options 3 and 4 have been discussed by others as to why they offer such poor performance.
Best Answer
The statement that "some bad cells may charge and discharge to the nominal capacity if they are charged immediately, but do not hold up after time" it is very slightly correct and it refers to the fact that the internal resistance varies slightly with different cells and after a VERY long time an imbalance will appear.
Just as mkeith said, all you need to do is measure the OCV (open circuit voltage) and match cells which are very close one to another and put them in series. Then put the closely matched series packs in parallel.