I am not sure how complicated it needs to be, but this seems to work to generate your output. I only changed your pairs line... (I took the liberty of putting Tim Robbins into Batman, just to give it more realistic overlap)
actorslist = [[u'Tim Robbins', u'Morgan Freeman', u'Bob Gunton', u'William Sadler'],
[u'Christian Bale', u'Heath Ledger', u'Tim Robbins', u'Michael Caine']]
import itertools
import pydot
graph = pydot.Dot(graph_type='graph', charset="utf8")
# generate a list of all unique actors, if you want that
# allactors = list(set([j for j in [i for i in actorslist]]))
# this is the key line -- you have to iterate through the list
# and not try to permute the whole thing
pairs = [list(itertools.permutations(k, 2)) for k in actorslist]
for pair in pairs:
for a,b in pair:
edge = pydot.Edge(a,b)
graph.add_edge(edge)
graph.write('dotfile.dot')
Output file (remember I changed the input re Tim Robbins)...
graph G {
charset=utf8;
"Tim Robbins" -- "Morgan Freeman";
"Tim Robbins" -- "Bob Gunton";
"Tim Robbins" -- "William Sadler";
"Morgan Freeman" -- "Tim Robbins";
"Morgan Freeman" -- "Bob Gunton";
"Morgan Freeman" -- "William Sadler";
"Bob Gunton" -- "Tim Robbins";
"Bob Gunton" -- "Morgan Freeman";
"Bob Gunton" -- "William Sadler";
"William Sadler" -- "Tim Robbins";
"William Sadler" -- "Morgan Freeman";
"William Sadler" -- "Bob Gunton";
"Christian Bale" -- "Heath Ledger";
"Christian Bale" -- "Tim Robbins";
"Christian Bale" -- "Michael Caine";
"Heath Ledger" -- "Christian Bale";
"Heath Ledger" -- "Tim Robbins";
"Heath Ledger" -- "Michael Caine";
"Tim Robbins" -- "Christian Bale";
"Tim Robbins" -- "Heath Ledger";
"Tim Robbins" -- "Michael Caine";
"Michael Caine" -- "Christian Bale";
"Michael Caine" -- "Heath Ledger";
"Michael Caine" -- "Tim Robbins";
}