laQie

Можно отфильтровать уже получившийся «product», я бы сделал как-то так:

from itertools import product

s = 'abcdefghijklmnopqrstuvwxyz1234567890.-'

comb = reduce(list.__add__,
              (map(''.join,
                   filter(lambda x: x[0] not in '.-' and x[-1] not in '.-',
                          product(s, repeat=i))) for i in xrange(1, 5)))
print len(comb)

Есть же документация по re, в которой все расписано.