How to prevent a video array from playing the same video twice?

If I understand this correctly, videos is a queue of videos that need to be played in order, then nothing else.

I would normalize all the queue management into the nextVideo() function, so that there was nothing special about the first time you play. Thus:

var videos = ["video1", "video2", "video3"]

var player1 = document.getElementById("video")
function setMp4Source1(theVideo) {
    var currentVideo = "videos/" + theVideo + ".mp4"
    player1.src = currentVideo
    player1.load()
    player1.play()
}
player1.addEventListener('ended', nextVideo, false)

function nextVideo() {
    let theVideo = videos.unshift()
    setMp4Source1(theVideo)
}
nextVideo() // start the chain here!

Now, this doesn't, as in your initial example, play a random video - just the next in the queue. You can play a random video and remove it from the queue by using splice() in nextVideo() as such:

function nextVideo() {
    let randomIndex = Math.floor(Math.random() * videos.length)
    let theVideo = videos[randomIndex]
    videos.splice(randomIndex,1) // remove 1 element starting at the index
    setMp4Source1(theVideo)
}

Of course, next you'll want to add a check to make sure you're not accessing an empty array...

function nextVideo() {
    if( videos.length < 1) {
       // no moar videos! :(
       // probably best to bail out here and avoid further chaining.
       // if you're clever, you'll add a placeholder image to let 
       // the user know there's no more videos.
       // maybe something from http://placekitten.com/
       player1.removeEventListener('ended', nextVideo, false)
       
       sizer_x = player1.clientWidth
       sizer_y = player1.clientHeight
       const kitty = '<img src="http://placekitten.com/' + sizer_x + '/' + sizer_y + '"/>'
       const kittyImg = document.createElement(kitty)
       player1.parentNode.replaceChild(kittyImg, player1)

       return
    }
    let randomIndex = Math.floor(Math.random() * videos.length)
    let theVideo = videos[randomIndex]
    videos.splice(randomIndex,1) // remove 1 element starting at the index
    setMp4Source1(theVideo)
}

Keep track of the index numbers played with a Set object. Set object is simular to an array but will only contain unique items. Details are commented in the following Snippet.

const videos = [
  "vs8s3.mp4", "vs12s3.mp4", "vs21s3.mp4", "vs2s3.mp4"
];
const player = document.querySelector("video");
// Create a Set object
const played = new Set();

function playVideo() {
  let current = Math.floor(Math.random() * videos.length);
  const base = 'https://glpjt.s3.amazonaws.com/so/av/';
  const source = base + videos[current];
  
  /* Check if video has already been played */
  // If Set {played} DOES NOT have the {current} index number...
  if (!played.has(current)) {
    // Add {current} index number to Set {played}
    played.add(current);
    player.src = source;
    player.play();
  } 
    /* or if Set {played} does have {current} index number AND Set {played} 
    DOES NOT have the same amount of numbers as Array {videos}... */
    else if (played.size != videos.length) {
    // Run the function again
    playVideo();
  } 
  // Otherwise end function
  else {
    return false;
  }
  /* OPTIONAL: Display the indexes of each video played in order */
  console.clear();
  console.log(JSON.stringify(Array.from(played)));
};

player.addEventListener('ended', playVideo, false);
player.addEventListener('click', playVideo, false);

video {
  cursor: pointer;
}

<video poster='http://simgbb.com/background/W46xw0TswdDx.jpg' width='360'></video>