Как из списка выбрать случайный элемент, но чтобы он не повторялся?
Перемешайте список с помощью random.shuffle() и выбирайте элементы последовательно.
Выбираете случайный элемент. Смотрите, не повторяется ли он.

import random
str_list = ["123", "eisdesn", "sjs38", "sjsklek"]

used = []

while len(used) != len(str_list):
    el = random.choice(str_list)
    if el not in used:
        print(el)
        used.append(el)

Либо
import random
str_list = ["123", "eisdesn", "sjs38", "sjsklek"]
for _ in range(len(str_list)):
    print(str_list.pop(random.randint(0, len(str_list)-1)))