Message notification for user

You need to use wp_ajax action to callback your function.

add_action( 'wp_ajax_update_last_seen_value', 'update_last_seen_value' );
function update_last_seen_value() {
    global $wpdb;
    $table="ej_users";
    $id = $_POST['id'];
    $meta_value = date('Y-m-d H:i:s');
    update_user_meta( $id , 'last_seen', $meta_value );
        $data = array(
            "status"     => 'success'
        );
    echo json_encode($data);
    die();
}

I have used your code and made correction to render scenario to my machine.

header.php file should be as per my understanding. You can make change as per your requirement.

<?php 
if(is_user_logged_in())
{
    $user_id = get_current_user_id();
    $meta_key = 'last_seen';
    if ( metadata_exists( 'user', $user_id, $meta_key ) ) 
    {
        $user_last_seen = get_user_meta( $user_id, $meta_key, true );
        if ( !empty($user_last_seen ))
        {  ?>
            <a href="javascript:void(0);" class="message-link"><p>New message</p></a>
            <input type="hidden" name="user_id" class="current-user-id" value="<?php echo get_current_user_id();?>">
            <?php
        }
    }
    else 
    {
        $meta_value = date('Y-m-d H:i:s');
        add_user_meta( $user_id, 'last_seen', $meta_value, true );
    }
}

jQuery snippet

   jQuery(".message-link").on('click', function () {
        var id = jQuery(".current-user-id").val();
        jQuery.ajax({
            type: 'POST',
            url: ajaxurl,
            data: {"action": "update_last_seen_value", "id": id},
            success: function (data) {
                console.log(data);
            }
        });
    });

Please check above code and let me know if you have any questions related this. I have tested and it is working fine for me.