Просто вызовите legend () с параметром labelpacing, вот пример:
import pylab as pl
pl.plot([0,1],[0,1], label="a")
pl.plot([0,2],[0,2], label="b")
pl.legend()
pl.savefig("p1.png")
pl.legend(labelspacing=2)
pl.savefig("p2.png")
Для повторного использования параметров:
import pylab as pl
pl.plot([0,1],[0,1], label="a")
pl.plot([0,2],[0,2], label="b")
params = dict(loc="right", prop=dict(size=9))
pl.legend(**params)
pl.savefig("p1.png")
params["labelspacing"] = 2
pl.legend(**params)
pl.savefig("p2.png")