Automatically assign taxonomy term if custom meta value exists

You should hook onto the save_post action.

add_action( 'save_post', 'add_video_taxonomy' );

function add_video_taxonomy( $post_id ) {

    // you should check if the current user can do this, probably against publish_posts
    // you should also have a nonce check here as well

    if( get_post_meta( $post_id, 'video_url', true ) ) {
        wp_set_post_terms( $post_id, 'video', 'your_custom_taxonomy_name', true );
    }

}