Exatamente com choice dá para fazer, deve importar o modulo random:

    import random

    cs = [2313, 2214, 2120]
    gav = [1101, 1103, 1104]
    icc = [3201, 3304, 3209]
    comp = [4101, 4203, 4409, 4559]

    disciplinas = [cs, gav, icc, comp]
    l = [0, 0, 2313, 1221, 0, 1333, 66, 0, 0, 0]

    randDisc = [] # armazenamos os resultados sorteados para mais tarde remove-los da lista disciplinas
    lCount = len(l)
    next1 = False
    for i in range(0, lCount-1):
        disc = random.choice(disciplinas)
        if(l[i] == 0 and l[i+1] == 0):
            l[i] = disc
            randDisc.append(disc)
            next1 = True
        elif(next1):
            l[i] = disc
            randDisc.append(disc)
            next1 = False

    if(next1): # ultimo elemento caso seja 0 seguido de outro (next1 definido no ultimo loop do ciclo)
        disc = random.choice(disciplinas)
        l[-1] = disc
        randDisc.append(disc)

    #aqui vamos remover os sorteados de disciplinas:
    randDisc = set(map(tuple,randDisc)) #removemos duplicados que possam haver
    for disc in randDisc:
        disciplinas.remove(list(disc))

    print(l) # [[3201, 3304, 3209], [2313, 2214, 2120], 2313, 1221, 0, 1333, 66, [4101, 4203, 4409, 4559], [4101, 4203, 4409, 4559], [2313, 2214, 2120]]
    print(disciplinas) #[[1101, 1103, 1104]]