from itertools import combinations, count

def interleave(a, b):
    empty = object()
    n = len(a) + len(b)
    # enumerate placements of a's items into n seats
    for a_indices in combinations(range(n), len(a)):
        L = [empty] * n
        for i, x in zip(a_indices, a): # put a's items into place
            L[i] = x
        it = iter(b)
        for i, x in enumerate(L): # fill empty seats with b's items
            if x is empty:
                L[i] = next(it)
        yield L
 
print(list(interleave([1,2], [3,4])))

def where(a, b, a_indices):
    """Yield a+b's items putting a's items at a_indices positions."""
    a, b, a_indices = iter(a), iter(b), iter(a_indices)
    ia = next(a_indices, -1)
    for i in count():
        if i == ia:
            yield next(a)
            ia = next(a_indices, -1)
        else:
            yield next(b)

def interleave_where(a, b):
    for a_indices in combinations(range(len(a) + len(b)), len(a)):
        yield where(a, b, a_indices)

print([list(g) for g in interleave_where([1,2], [3,4])])