Si no quieres que se modifique tu lista `Einicial` debes hacer una copia en profundida de ella y no:

    izq_inicial = Einicial

Con esto solo haces que ambas variables referencien al mismo objeto en memoria, por lo tanto modificar una implica modificar la otra (son el mismo objeto `list`). Para crear una copia en profundidad (deep copy) usa [`copy.deepcopy`][1]:

    import copy
    import math
    import Queue
    
    
    Uinicial = raw_input("Ingrese numeros aleatoriamente del 0-8: ")
    Einicial = map(int, str(Uinicial))
    Efinal = [1,2,3,4,5,6,7,8,0]
    posicion_de_cero = Einicial.index(0)
    cola = Queue.Queue()
    
    
    def movimiento_izquierda(posicion_de_cero,Einicial):
        #Movimiento hacia a la Izquierda
        Einicial
        izq_inicial = copy.deepcopy(Einicial)
        print izq_inicial
        new_posicion_izquierda = posicion_de_cero - 1
        izq_inicial[posicion_de_cero], izq_inicial[new_posicion_izquierda] = izq_inicial[new_posicion_izquierda], izq_inicial[posicion_de_cero]
        print izq_inicial
    
    def movimiento_derecha(posicion_de_cero,Einicial):
        #Movimiento hacia a la derecha
        der_inicial = copy.deepcopy(Einicial)
        print der_inicial
        new_posicion_derecha = posicion_de_cero + 1
        der_inicial[posicion_de_cero], der_inicial[new_posicion_derecha] = der_inicial[new_posicion_derecha], der_inicial[posicion_de_cero]
        print der_inicial
    
    movimiento_izquierda(posicion_de_cero,Einicial)
    movimiento_derecha(posicion_de_cero,Einicial)


  [1]: https://docs.python.org/2/library/copy.html