Add or remove HTML class with selective refresh?

Yes. This can be accomplished by creating a custom selective refresh Partial type, and overriding the refresh method in the JavaScript class.

Here’s the relevant JavaScript which should get enqueued in the Customizer preview, with customize-selective-refresh as its script dependency:

wp.customize.selectiveRefresh.partialConstructor.body_class = wp.customize.selectiveRefresh.Partial.extend({

    /**
     * Class name choices.
     *
     * This is populated in PHP via `wp_add_inline_script()`.
     *
     * @type {Array}
     */
    choices: [],

    /**
     * Refresh partial.
     *
     * Override refresh behavior to bypass partial refresh request in favor of direct DOM manipulation.
     *
     * @returns {jQuery.Promise} Resolved promise.
     */
    refresh: function() {
        var partial = this, setting, body, deferred, className;

        setting = wp.customize( partial.params.primarySetting );
        className = setting.get();
        body = $( document.body );
        body.removeClass( partial.choices.join( ' ' ) );
        body.addClass( className );

        // Do good diligence and return an expected value from the function.
        deferred = new $.Deferred();
        deferred.resolveWith( partial, _.map( partial.placements(), function() {
            return '';
        } ) );
        return deferred.promise();
    }
});

Then you can make use of this custom type when you register the partial in PHP:

$wp_customize->selective_refresh->add_partial( 'nav_body_class', array(
    'selector' => 'nav',
    'type' => 'body_class',
) );

Here is a full working plugin that demonstrates the technique: https://gist.github.com/westonruter/731e3106177ce2b067290ddbe602ce05