[Arigato]

Где-то в начале батника должна быть команда:

setlocal enabledelayedexpansion

Я так понимаю, она у вас имеется, просто не все скопировано сюда.

Далее тут:

call set "randomFile=!pyti_k_15_perebivkam[%randomIndex%]!"

Переменная %randomIndex% раскрывается до начала цикла, так как заключена в знаки %, потому она имеет исходное значение 3 на всех итерациях цикла.

Для разыменования надо вынести этот код в отдельную подпрограмму. Вот так работает:

@echo off
setlocal enabledelayedexpansion
set i=0
for %%x in (1 2 3 4 5 6 7 8 9 10 11 12 13 14 15) do (
	set /A i+=1
	set pyti_k_15_perebivkam[!i!]=vidov_ska4ali_%%x.mp4
)

for /L %%x in (1,1,15) do (
	echo !pyti_k_15_perebivkam[%%x]!
)

echo ************

set randomIndex=3
set "skolkoShtykPerebivok=2"
for /L %%x in (1,1,!skolkoShtykPerebivok!) do (
	set /a randomIndex=!random! %% 15 + 1
	echo !randomIndex!
	call :randomFile
	set "imena_perebivok_dla_dobavleniya=!imena_perebivok_dla_dobavleniya! !randomFile!"
)


echo imena_perebivok_dla_dobavleniya !imena_perebivok_dla_dobavleniya!

:randomFile
	set "randomFile=!pyti_k_15_perebivkam[%randomIndex%]!"
exit /b