| это метасимвол регулярного выражения; если вы хотите разделить на литерал |, вы должны экранировать его в \|, который в качестве строкового литерала Java является "\\|".
Исправлено:
template.split("\\|")
О лучшем алгоритме
Вместо вызова remove по одному со случайными индексами, лучше сгенерировать достаточное количество случайных чисел в диапазоне, а затем обойти List один раз с помощью listIterator(), вызывая remove() по соответствующим индексам. В stackoverflow есть вопросы о том, как генерировать случайные, но разные числа в заданном диапазоне.
При этом ваш алгоритм будет O(N).
Ответ 2
Это меня раздражало много раз. Arrays.asList создает неизменяемый список. Из Javadoc: возвращает список фиксированного размера, поддерживаемый указанным массивом.
Создайте новый список с тем же содержимым:
newList.addAll(Arrays.asList(newArray));
Это создаст немного дополнительного мусора, но вы сможете изменить его.