Substitute a Li-ion Polymer Battery with AA(A)s
If you can make them fit, either 3 AA or AAA would work, but unless you know the circuit, you should stick as close to the existing battery voltage and capacity as possible.  That would mean you have to look at the NiCD or NiMH batteries only, as they are 1.2V per cell.

Given a choice, I'd go with the NiMH option, as not only will you get the 1.2V per cell, or 3.6V in series, but you will also get almost the same capacity as the existing LiP battery currently. 

With either of the above batteries, you will need to recharge them externally, or modify the charging circuit of your device.

The above is from making the assumption that you want to stay away from Li-ion Polymer batteries, as stated in your question.  If it is only that particular one that you want to avoid, but don't mind working with them, the best option in an AA or AAA case would obviously be an AA Li-ion Polymer cell. 3.7V per cell, the same capacity, and rechargable by the same circuit as the original.