Adding tag slug to post permalink

You need to add a new tag (e.g. %tag%) that you can use in post links.
One possibility is to use the add_rewrite_tag() function.

Then use the post_link filter to replace the %tag% in the link with the appropriate value.

Finally, change the post link structure in the settings.

Settings -> Permalinks -> Custom Structure:
/%category%/%tag%/%postname%/

Optionally, using available_permalink_structure_tags filter, you can add a new tag to the list of available tags, which is visible on the settings page.

add_action( 'init', 'se416974_tag_in_permalink' );

function se416974_tag_in_permalink()
{
    add_rewrite_tag( '%tag%', '([^/]+)' );
    add_filter( 'post_link',  'se416974_post_link', 20, 2 );
}

function se416974_post_link( $link, $post )
{
    if ( FALSE === stripos($link, '%tag%') )
        return $link;
    $tags = get_the_tags( $post->ID );
    if ( !is_array($tags) || 0 == count($tags) )
        return str_replace( '%tag%', 'no-tag', $link );

    $first_tag = current( $tags );
    $new_link = str_replace( '%tag%', $first_tag->slug, $link );
    return $new_link;
}

function se416974_available_tags( $available_tags )
{
    $available_tags['tag'] = '%s (One of tags assigned to post)';
    return $available_tags;
}