Add a custom walker to a menu created in a widget

If you look at implementation of WP_Nav_Menu_Widget class you will see the following code:

function widget($args, $instance) {
    // Get menu
    $nav_menu = ! empty( $instance['nav_menu'] ) ? wp_get_nav_menu_object( $instance['nav_menu'] ) : false;

    if ( !$nav_menu )
        return;

    $instance['title'] = apply_filters( 'widget_title', empty( $instance['title'] ) ? '' : $instance['title'], $instance, $this->id_base );

    echo $args['before_widget'];

    if ( !empty($instance['title']) )
        echo $args['before_title'] . $instance['title'] . $args['after_title'];

    wp_nav_menu( array( 'fallback_cb' => '', 'menu' => $nav_menu ) );

    echo $args['after_widget'];
}

It means that there is no any chance to hook a menu. So you need to take a look at wp_nav_menu function implementation, where you can find following lines of code:

$defaults = array(
  'menu' => '',
  'container' => 'div',
  'container_class' => '',
  'container_id' => '',
  'menu_class' => 'menu',
  'menu_id' => '',
  'echo' => true,
  'fallback_cb' => 'wp_page_menu',
  'before' => '',
  'after' => '',
  'link_before' => '',
  'link_after' => '',
  'items_wrap' => '<ul id="%1$s" class="%2$s">%3$s</ul>',
  'depth' => 0,
  'walker' => '',
  'theme_location' => ''
);

$args = wp_parse_args( $args, $defaults );
$args = apply_filters( 'wp_nav_menu_args', $args );
$args = (object) $args;

Here you can see that all arguments passed to the wp_nav_menu function could be replaced. So what you need is to create your own hook handler which will add your walker to a navigation menu. It could be simple as:

function myplugin_custom_walker( $args ) {
    return array_merge( $args, array(
        'walker' => new My_Custom_Walker(),
        // another setting go here ... 
    ) );
}
add_filter( 'wp_nav_menu_args', 'myplugin_custom_walker' );