1] VOLTAGE: 3.6V or 3.7V - 18650 Li Ion Batteries
All single cell lithium ion batteries are going to be 3.6-3.7v. There are applications where multiple cells will be tied together in series. This will result in voltages that are multiples of 3.6-3.7v. So as long as you match the number of cells and approximate mAH you should be fine.
2] Possible Voltage Shortage?
The voltages and battery life responses for all batteries are going to have slight difference. For the most part this won't matter. Most projects that use batteries are not terribly voltage dependent. They will either boost or regulate their voltage to get the voltage they want out, or they will be able to run at a wide range.
As a note, "Shortage" in this context usually means you are creating a short across your battery. Might want to be careful with that terminology.
3] Fundamental Reason for this Voltage Range
I am not an expert on this, but I know it deals with the chemistry of the battery itself.
4] Parallel Cell Charging - One BIG Li-Ion Battery Pack
This can be done. There are some issues that can come up when doing it. This might be worthy of a question by itself. If you do ask, might want to ask if the same can be done for packs in series.
5] Charging... How?
Same as previous answer.
I'm going to address the larger issue of making the system robust and reliable, rather than just focusing on the batteries. The main issues that I see are: ruggedness, waterproofness, battery/charging, and the "chassis".
If I were building these things myself, I would use PVC pipe as the chassis. But more on this in a moment.
To increase ruggedness, I would encase the PCB in "casting resin". Just google "casting resin". Essentially it is an epoxy that you can pour into the PVC pipe to encase the PCB's to both waterproof them and support the PCB against shock and vibration. Casting resin is available from many hobby/craft stores like Michaels and Hobby Lobby. Just put your electronics in the PVC pipe, mix up the resin, and pour it into the pipe. Important Note: casting resin comes in 2 parts and the ratio of the two parts effects how long it takes to harden. The faster it hardens the HOTTER it gets during the curing process. You want it to harden as slowly as possible, otherwise it might get hot enough to damage the electronics. Experimentation with the resin is important to getting this right.
Casting resin will work best if your batteries are rechargeable and fully encased in the resin. However, I wouldn't do that. Batteries behave weirdly when charged. Best case your batteries could get hot and not be able do dissipate the heat due to the resin. Worst case, your batteries build up some internal pressure that can't be dealt with due to being encased. As an alternative, you could use some super-capacitors. The usefulness of super-caps will depend on your power consumption and a variety of other issues, but I've used them for several applications and they work quite nicely. Essentially, supercaps behave like rechargeable batteries except that they don't hold as much power but they can be charged and discharged almost an unlimited number of times.
If you can't use supercaps, then rechargeable batteries with tabs/pins/wires already attached would be your 2nd best choice. 3rd choice would be standard or rechargeable AA's. With AA's, I personally wouldn't spend much time making the spring keep good contact. That is a massive waste of time because whatever you do, it won't be good enough! Instead, your design should take that into account. The best way to do this is to simply put large-ish caps in your circuit so that if the batteries do momentarily loose contact then the circuit will remain powered up.
If you use supercaps or rechargeable batteries then next comes the charging system. You could simply have a connector that goes to a charger. Of course that isn't very waterproof. A cool way would be to have a non-contact inductive charger. Imagine a transformer with two coils of wire. AC goes into one coil and comes out the other coil. An inductive charger is the same, except that one coil is in the base of your baton and the other coil is in the "charging station".
In the best case everything-- including super caps, charging coil, and PCB's-- could be encased in casting resin. With no seams there is no way for water to get into the circuitry! And with everything encased and fully supported the whole thing is very mechanically robust. With a little bit of work, you wouldn't even need end-caps on the PVC pipe. That way your baton would be a simple and smooth rod. I'd bet that you could take this and throw it out of a low-flying plane and it would survive.
Also, Casting resin is water-clear. Your circuit can have status LED's that can be seen through the resin.
Best Answer
The problem with 26650 batteries is they're not normally intended to be interchangeable like AA batteries. They are most often found with solder tabs spot welded to the ends and either hard wired into a battery pack (such as for a laptop battery) or soldered direct to a PCB.
Being rechargeable they don't need replacing, so there is no need to add the expense of a battery holder.
However, that doesn't mean it's impossible.
You can buy PCB mount contacts for AA batteries, which are similar in size, such as these: http://uk.farnell.com/keystone/590/battery-holder-aa-n-1way/dp/1339844 and build up your own battery holder on a PCB. You may need to adjust the sprung leaf a little to get to the right level for the battery contact, but it's certainly a possibility. You would, of course, need some side support to keep the battery in place, but I'm sure a creative mind like yours could come up with something that would work.