Getting a 404 on single custom post type page when using rewrite on a custom taxonomy

Add priority with at least 1 to your add actions:

add_action( 'init', 'add_training_post_type', 1 );
add_action( 'init', 'create_training_taxonomies', 1 );

Currently your issue is that your post type and taxonomy rewrite slugs are identical, so the URL base would be the same and it confuses WP. Fortunately there is easy solution, just add this code to your functions.php file

function taxonomy_slug_rewrite($wp_rewrite) {
    $rules = array();
    // get all custom taxonomies
    $taxonomies = get_taxonomies(array('_builtin' => false), 'objects');
    // get all custom post types
    $post_types = get_post_types(array('public' => true, '_builtin' => false), 'objects');

    foreach ($post_types as $post_type) {
        foreach ($taxonomies as $taxonomy) {

            // go through all post types which this taxonomy is assigned to
            foreach ($taxonomy->object_type as $object_type) {

                // check if taxonomy is registered for this custom type
                if ($object_type == $post_type->rewrite['slug']) {

                    // get category objects
                    $terms = get_categories(array('type' => $object_type, 'taxonomy' => $taxonomy->name, 'hide_empty' => 0));

                    // make rules
                    foreach ($terms as $term) {
                        $rules[$object_type . "https://wordpress.stackexchange.com/" . $term->slug . '/?$'] = 'index.php?' . $term->taxonomy . '=' . $term->slug;
                    }
                }
            }
        }
    }
    // merge with global rules
    $wp_rewrite->rules = $rules + $wp_rewrite->rules;
}
add_filter('generate_rewrite_rules', 'taxonomy_slug_rewrite');

And to be safe i would go to your permalinks page and just press save button to be sure.