Wordpress - 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' );

Expanding on @Eugene's answer, if you want to limit this to a specific menu, just check the term ID of the menu:

function custom_nav_args($args){
$menu = $args['menu'];
    if($menu->term_id === 17)  /* replace term_id with menu id, or use $menu->name to do it by menu name*/
    {
        $args['walker'] = new My_Custom_Walker();
    }
    return $args;
}
add_filter('wp_nav_menu_args', 'custom_nav_args');

This is an alternative to targeting a menu by term_id and I thought it might be of use to someone as a way of modifying several menus without having to look up their ids.

By adding print_r($args) to a filter, I noticed that $args['menu'] is a string for menus in predefined theme locations and WP_Term_Object for a custom menu widget in a sidebar.

I used this to target menus by slug and add a class to their container. A number of menus can be targeted by including a common string in their slugs. Note: menu slug comes from the array key in register_nav_menus().

function my_menu_thingy( $args ) {
  if( is_object($args['menu']) && strpos($args['menu']->{slug},'my-common-string') !== false ) {
    $args['walker'] = new My_Custom_Walker();
  }
  return $args;
}
add_filter( 'wp_nav_menu_args', 'my_menu_thingy' );

For a single menu you would just need to check that $args['menu']->{slug} == 'your-slug' instead of the strpos() bit above.