Update the ticks and the tick labels:

cbar.set_ticks([mn,md,mx])
cbar.set_ticklabels([mn,md,mx])

import matplotlib.pyplot as plt
import numpy as np
from matplotlib.colors import ListedColormap

#discrete color scheme
cMap = ListedColormap(['white', 'green', 'blue','red'])

#data
np.random.seed(42)
data = np.random.rand(4, 4)
fig, ax = plt.subplots()
heatmap = ax.pcolor(data, cmap=cMap)

#legend
cbar = plt.colorbar(heatmap)

cbar.ax.get_yaxis().set_ticks([])
for j, lab in enumerate(['$0$','$1$','$2$','$>3$']):
    cbar.ax.text(.5, (2 * j + 1) / 8.0, lab, ha='center', va='center')
cbar.ax.get_yaxis().labelpad = 15
cbar.ax.set_ylabel('# of contacts', rotation=270)


# put the major ticks at the middle of each cell
ax.set_xticks(np.arange(data.shape[1]) + 0.5, minor=False)
ax.set_yticks(np.arange(data.shape[0]) + 0.5, minor=False)
ax.invert_yaxis()

#labels
column_labels = list('ABCD')
row_labels = list('WXYZ')
ax.set_xticklabels(column_labels, minor=False)
ax.set_yticklabels(row_labels, minor=False)

plt.show()

You were very close. Once you have a reference to the color bar axis, you can do what ever you want to it, including putting text labels in the middle. You might want to play with the formatting to make it more visible.

You can keep the same locators as proposed by the colorbar function but change the ticklabels in order to print the formatted date as follows:

# change colobar ticks labels and locators 
cbar.set_ticks([s.colorbar.vmin + t*(s.colorbar.vmax-s.colorbar.vmin) for t in cbar.ax.get_yticks()])
cbar.set_ticklabels([mdates.datetime.datetime.fromtimestamp((s.colorbar.vmin + t*(s.colorbar.vmax-s.colorbar.vmin))/1000000000).strftime('%c') for t in cbar.ax.get_yticks()])
plt.show()

which gives the result below:

If you really want to control tick locations, you can compute the desired values (here for approximately 3 months intervals ~91.25 days):

i,ticks = 0,[s.colorbar.vmin]
while ticks[-1] < s.colorbar.vmax:
   ticks.append(s.colorbar.vmin+i*24*3600*91.25*1e9)
   i = i+1
ticks[-1] = s.colorbar.vmax
cbar.set_ticks(ticks)
cbar.set_ticklabels([mdates.datetime.datetime.fromtimestamp(t/1e9).strftime('%c') for t in ticks])

You are suffering from an off-by-one error. You have 10 ticklabels spread among 11 colors. You might be able to correct the error by using np.linspace instead of np.arange. Using np.linspace the third argument is the number of values desired. This reduces the amount of mental gymnastics needed to avoid the off-by-one error:

import matplotlib.pyplot as plt
import numpy as np
import matplotlib.cm as cm
import matplotlib.colors as mcolors

def colorbar_index(ncolors, cmap):
    cmap = cmap_discretize(cmap, ncolors)
    mappable = cm.ScalarMappable(cmap=cmap)
    mappable.set_array([])
    mappable.set_clim(-0.5, ncolors+0.5)
    colorbar = plt.colorbar(mappable)
    colorbar.set_ticks(np.linspace(0, ncolors, ncolors))
    colorbar.set_ticklabels(range(ncolors))

def cmap_discretize(cmap, N):
    """Return a discrete colormap from the continuous colormap cmap.

        cmap: colormap instance, eg. cm.jet. 
        N: number of colors.

    Example
        x = resize(arange(100), (5,100))
        djet = cmap_discretize(cm.jet, 5)
        imshow(x, cmap=djet)
    """

    if type(cmap) == str:
        cmap = plt.get_cmap(cmap)
    colors_i = np.concatenate((np.linspace(0, 1., N), (0.,0.,0.,0.)))
    colors_rgba = cmap(colors_i)
    indices = np.linspace(0, 1., N+1)
    cdict = {}
    for ki,key in enumerate(('red','green','blue')):
        cdict[key] = [ (indices[i], colors_rgba[i-1,ki], colors_rgba[i,ki])
                       for i in xrange(N+1) ]
    # Return colormap object.
    return mcolors.LinearSegmentedColormap(cmap.name + "_%d"%N, cdict, 1024)

fig, ax = plt.subplots()
A = np.random.random((10,10))*10
cmap = plt.get_cmap('YlGnBu')
ax.imshow(A, interpolation='nearest', cmap=cmap)
colorbar_index(ncolors=11, cmap=cmap)    
plt.show()

A better solution is

from matplotlib.ticker import FuncFormatter

fmt = lambda x, pos: '{:.1%}'.format(x)
cbar = plt.colorbar(format=FuncFormatter(fmt))