If one meta key value is empty, try to get another meta key, and if both meta keys are empty show something else?

You can use if else:

<div class="video-embed" style="margin-top: 0px; z-index:102; margin-bottom: 0px;">

<?php

$url1 = get_post_meta( $post->ID , 'video_play' , true ) ?: get_post_meta( $post->ID , 'video_stop' , true ) ?: false;

if( $url1 ):
    $search="#(.*?)(?:href="https://wordpress.stackexchange.com/questions/302040/https?://)?(?:www\.)?(?:youtu\.be/"youtube\.com(?:/embed/|/v/|/watch?.*?v=))([\w\-]{10,12}).*#x";
    $replace="http://www.youtube.com/embed/$2";
    $url        = preg_replace($search,$replace,$url1);

?>

<iframe width="560" height="315" src="<?php echo $url; ?>" frameborder="0" allow="autoplay; encrypted-media" allowfullscreen></iframe>
<?php 
else: 
    echo "This video is removed";
endif;    
?>
</div>