How exactly does a battery work (specifically Pb/H2SO4/H2SO4/PbO2 lead acid battery)? Specifically talking about the lead-acid battery, I understand (or think I understand) this much: 
The anode, in the presence of the electrolyte, $\ce{H2SO4}$ will be oxidised:
$$\ce{Pb (s) + SO4^2- (aq) -&gt; PbSO4 (s) + 2e-}$$

At the same time at the $\ce{PbO2}$ electrode, two electrons from the $\ce{PbO2}$ solid are lost to the electrolyte: 
$$\ce{PbO2 (s) + 2e- + 4H+ (aq) + SO4^2-(aq) -&gt; PbSO4 (s) + 2H2O}$$

This all occurs without a solid conductive path (say a wire) between the anode and cathode, the cathode will build a positive charge while the anode builds a negative charge and ions will diffuse appropriately during this process.

When a wire is connected between the anode and cathode, electrons that have built up on the surface of the $\ce{Pb}$ will migrate to the $\ce{PbO2}$ which is of lower potential and if a load is placed along the way work can be done. 
So batteries will discharge by themselves without even contributing to any work? Is this not true for all batteries? 

The part that confuses me is that most people say that batteries store chemical energy. 

I understand that the redox reactions release energy which can be used as electrical energy but if batteries discharge without contributing to any meaningful work then why are they still considered to be storing energy? Aren't they converting chemical energy to heat continually unless they are put to use?
In order for oxidation-reduction chemical reactions to occur, the electrons must somehow go from the anode electrode where the oxidizing (electron donor) takes place to the cathode electrode where the reducing (electron acceptance) occurs.

Ideally, the electrolyte, in this case sulfuric acid, should allow the movement of positively charged ions but prevent the movement of electrons through it.  This forces the electrons to go through a circuit, external to the cell, to go from anode to cathode thus enabling the redox to occur.  Without electron flow, said redox reaction will not occur.

In the real world, there will be some leakage current through the electrolyte and other parts of battery.  We can eliminate the leakage with a more insulating electrolyte, but this would hurt the charging process and make the battery less rechargeable.  So, what we have is an economical compromise.