Y a plusieurs solutions qui s'offrent à toi.
Mais là vue que ce que tu demandes c'est à base de " tirage sans remise ", bah faut voir ton ensemble de lettres (hors première et dernière) comme un sac, et à chaque fois, tu en tires une aléatoire, et tu la retires du sac.
Au hasard ça peut donner un truc du genre en Python :
#Ton sac
bag = []
#Tu ajoutes le traitement pour ajouter toutes les lettres à ton sac (sous forme de liste dans cet exemple)
#Ta nouvelle chaine
new_str = ""
while bag: #Tant que le sac n'est pas vide
new_str += tirerUneLettre(bag) #On ajoute à la nouvelle chaine une lettre tirée du sac, et on oublie pas de retirer la lettre tirée de la liste (principe de " pop ")
Voilà un code tout con, à toi de voir comment tu gères ton aléatoire, et ne pas oublier de rajouter la première et la dernière lettre à ta nouvelle string. 