wp_nav_menu custom walker class

You can try to alter the $attributes string, since that outputs the attributes in the a tag. The following is untested:

$myClass="some-custom-class";
$myClassAdded = false;
$attributes="";
foreach ( $atts as $attr => $value ) {
    if ( ! empty( $value ) ) {
        $value = ( 'href' === $attr ) ? esc_url( $value ) : esc_attr( $value );
        if( $attr == 'class' ){
            $value .= ' ' . $myClass;
            $myClassAdded = true;
        }
        $attributes .= ' ' . $attr . '="' . $value . '"';
    }
}
if( !$myClassAdded ){
     $attributes .= ' class="' . $myClass . '"';
}

I also added an extra boolean in case the class attribute is never found in the loop.