Do brand new rechargeable batteries have a charge?
When a standard Duracell AA battery is manufactured, it contains all the charge it will ever have (right?), and can't be recharged.

Correct, the energy in the cell is there because of the chemical reaction. The cell is made with these chemicals. The chemical reaction which produces electricity cannot be reveresed. Therefore these cells cannot be charged. Engineers call these "Primary cells".

NiCd cells

NiCd cells are almost obsolete these days because of the Cadmium which is a nasty chemical. NiCd cells do suffer from leakage meaning they discharge by themselves even when not in use. So if a NiCd cell is charged, after a few weeks to months it will be empty anway. The good thing is that NiCd cells do not care about a complete discharge, you can just charge them again and they should work as new.

NiMh cells

NiMh cells are quite similar to NiCd cells but have a higher capacity for the same size without the nasty Cadmium. On most NiMh cells self-discharge is even worse than NiCd cells. So the same applies: after a few weeks to months it the cell will be empty. As with NiCd cells you can just recharge again and theyŕe good to go.

NiMh LSD (Low Self Discharge) cells

NiMh LSD cells (often is says "Ready to use" on the packaging) are similar to NiMh cells but with improved self discharge. Most will still be 80% charged after 6 months of storage. My guess is that these cells are produced in a state of full charge, similar to primary cells. Charging each cell would take too much time and money.

Lithium cells like in Laptops/smartphone

These will contain a certain charge at manufacturing. The optimum charging level is around 40%, higher and lower values stress the battery more and would limit the battery's lifetime. A full-discharge is very harmful for Lithium based cells, it is best to avoid that. Lithium based cells suffer very little from self discharge so that 40% charge can be kept for a long time in storage. If these cells would have to be (dis)charged to 40% charge in manufacturing that would take a lot of time, power (or power lost) and chargers and therefore it would be expensive. I'm no expert on this but I expect that the Lithium cells are produced such that they are at 40% charge level (or slightly higher) already.