Изменяю ответ в связи с тем, что нашёл решение.
На ответ натолкнул комментарий товарища
Roman
В общем решение состоит из двух частей:
1. Оставить массив строк в покое. Пусть он будет в том виде, в котором задан изначально.
2. Дополнительно создаём массив чисел, который будет хранить индексы и после выборки случайного индекса делаем "сортировку" (это скорее сдвиг одного элемента, но всё же) уже в массиве индексов
int index = random(0, LastStringCount );
result = StringList[Indexes[index]];
int j = 0;
for(int i = 0; i < LastStringCount ; i++) {
if (i != index) {
Indexes[j] = Indexes[i];
Serial.println(Indexes[j]);
j++;
}
}