Примените значение css с помощью jQuery, но проверьте, не указано ли оно уже

let urls = [
  'https://source.unsplash.com/5E5N49RWtbA/300x300',
  'https://source.unsplash.com/G85VuTpw6jg/300x300',
  'https://source.unsplash.com/fIq0tET6llw/300x300',
  'https://source.unsplash.com/P_0R02ArdLE/300x300',
  'https://source.unsplash.com/PC_lbSSxCZE/300x300',
  'https://source.unsplash.com/nptLmg6jqDo/300x300',
  'https://source.unsplash.com/1_CMoFsPfso/300x300',
  'https://source.unsplash.com/mk7D-4UCfmg/300x300'
];

// Get reference to divs and assign images on inital load
let images = $('.image');
let unusedDivs;

images.each(function(i, e) {
  jQuery(this).css('background-image', `url(${urls[i]})`);
  jQuery(this).data("image-index", i).data("div-used", false);
});

let lastImageIndex = null;

setInterval(function() {
  // Get indexes that are already in ue
  const usedIdx = images.map(function(i, e) {
    return jQuery(e).data("image-index");
  }).get();

  // Filter indexes of urls that are not displayed yet
  const unusedIdx = [];
  urls.forEach(function(url, i) {
    if (usedIdx.indexOf(i) == -1)
      unusedIdx.push(i);
  });

  // get images div that not in use yet
  unusedDivs = jQuery('.image').filter(function(i, e) {
    return $(e).data("div-used") == false;
  });

  // Choose a random index from the unused indexes array
  const randUnsedIdx = Math.floor(Math.random() * unusedIdx.length);

  // Chose a random image div to apply image to
  const randDivIdx = Math.floor(Math.random() * unusedDivs.length);
  const current = unusedDivs.eq(randDivIdx);
  lastImageIndex = randDivIdx;

  // Get index number
  const imgUrlIdx = unusedIdx[randUnsedIdx];

  // fade out old image then on callback set the url of the new image
  // then fade it in and assign the index to the dive so in next 
  // iteration we can filter it out
  current.fadeOut(400, function() {
    current.css('background-image', `url(${urls[imgUrlIdx]})`);
    current.fadeIn();
    current.data("image-index", imgUrlIdx).data("div-used", true);
    
    // if all unsed divs have been used then reset
    if (unusedDivs.length == 1)
      jQuery('.image').data("div-used", false);

  });

}, 2000);

body {
  margin: 0;
  font-size: 0;
}

.image {
  background-size: cover;
  display: inline-block;
  width: 23%;
  padding-top: 23%;
  margin: 1%;
}

<script src="https://cdnjs.cloudflare.com/ajax/libs/jquery/3.3.1/jquery.min.js"></script>
<div id="images">
  <div class="image"></div>
  <div class="image"></div>
  <div class="image"></div>
  <div class="image"></div>
  <div class="image"></div>
</div>

var urls = [
        	'url(https://placekitten.com/g/350/150)',
        	'url(https://placekitten.com/g/300/550)',
        	'url(https://placekitten.com/g/400/200)',
        	'url(https://placekitten.com/g/350/750)',
        	'url(https://placekitten.com/g/250/600)',
        	'url(https://placekitten.com/g/400/150)',
        	'url(https://placekitten.com/g/300/600)',
        	'url(https://placekitten.com/g/450/350)'
    	  ];
    	  // Select the next image
        var selectedImages = [1,2,3,4] // initial state of divs img urls
        var lastSelectedDiv = -1; // initial state of last selected div

    	  setInterval(function() {
    	  var active; 
        do{
          active = Math.floor(Math.random() * (urls.length - 2)) + 1
        } while(selectedImages.indexOf(active) != -1) // get a unique image (not in current ones that are displayed)
    		// Select randomnly the next div to change which is diffrent than the lastSelectedDiv
        var rand;
        do{
    		  rand = Math.floor(Math.random() * 4); // get a random value until its not the same as lastSelectedDiv
        } while(rand == lastSelectedDiv)
        selectedImages[rand] = active;

        lastSelectedDiv = rand; // override lastSelectedDiv to new random value so that next time it must be different
    		let current = $('.image:nth-child('+(rand+1)+')');
    		
    		current.toggleClass("show hide");
    		
    		// The fade effect takes 400ms
    		
    		setTimeout(function(){
    		
    		  current.css('background-image', urls[active]);
      
    		
    		  current.toggleClass("hide show");
    		
    		},400);

    		
    	  }, 2000);

body { margin: 0; font-size: 0;}

    .image {
      background-size: cover;
      display: inline-block;
      width: 23%;
      padding-top: 23%;
      margin: 1%;
      transition: opacity 0.4s ease;
    }

    .image:nth-of-type(1) { 
      background-image: url(https://placekitten.com/g/350/150); 
    }
    .image:nth-of-type(2) { 
      background-image: url(https://placekitten.com/g/300/550); 
    }
    .image:nth-of-type(3) { 
      background-image: url(https://placekitten.com/g/400/200); 
    }
    .image:nth-of-type(4) { 
      background-image: url(https://placekitten.com/g/350/750); 
    }

    .show {
          opacity: 1;
    }

    .hide {
      opacity: 0;
    }

    <script src="https://cdnjs.cloudflare.com/ajax/libs/jquery/2.2.4/jquery.min.js"></script>
    <div id="images">
      <div class="image"></div>
      <div class="image"></div>
      <div class="image"></div>
      <div class="image"></div>
    </div>