colorbar() accepts a cax keyword argument that allows you to specify the axes object that the colorbar will be drawn on.

In your case, you would change your colorbar call to the following:

# colorbar
axes = plt.subplot2grid((4, 2), (0, 1), rowspan=3)
plt.colorbar(pc, cax=axes)

This will take up the whole space given by subplot2grid; you can adjust this to be more reasonable either by having the main axes take up many more columns than the colorbar axes, or by setting up the gridspec explicitly. For example, your figure may be easier to tweak with the following:

from matplotlib import gridspec
gs = gridspec.GridSpec(2, 2, height_ratios=(3, 1), width_ratios=(9, 1))

# first graph
axes = plt.subplot(gs[0,0])
pc = plt.pcolor(df1, cmap='jet')

# second graph
axes = plt.subplot(gs[1,0])
plt.pcolor(df2, cmap='Greys')

# colorbar
axes = plt.subplot(gs[0,1])
plt.colorbar(pc, cax=axes)

Then you can just change height_ratios and width_ratios to your liking.

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.

Using vmin and vmax forces the range for the colors. Here's an example:

import matplotlib as m
import matplotlib.pyplot as plt
import numpy as np

cdict = {
  'red'  :  ( (0.0, 0.25, .25), (0.02, .59, .59), (1., 1., 1.)),
  'green':  ( (0.0, 0.0, 0.0), (0.02, .45, .45), (1., .97, .97)),
  'blue' :  ( (0.0, 1.0, 1.0), (0.02, .75, .75), (1., 0.45, 0.45))
}

cm = m.colors.LinearSegmentedColormap('my_colormap', cdict, 1024)

x = np.arange(0, 10, .1)
y = np.arange(0, 10, .1)
X, Y = np.meshgrid(x,y)

data = 2*( np.sin(X) + np.sin(3*Y) )

def do_plot(n, f, title):
    #plt.clf()
    plt.subplot(1, 3, n)
    plt.pcolor(X, Y, f(data), cmap=cm, vmin=-4, vmax=4)
    plt.title(title)
    plt.colorbar()

plt.figure()
do_plot(1, lambda x:x, "all")
do_plot(2, lambda x:np.clip(x, -4, 0), "<0")
do_plot(3, lambda x:np.clip(x, 0, 4), ">0")
plt.show()