custom menu widget where menu title is a link

You can filter the title of most widgets and change the markup. The name of the filter is 'widget_title' and the third parameter tells you the type of the filtered widget.

Sample code, not tested:

add_filter( 'widget_title', 'wpse_52108_nav_widget_title_link', 30, 3 );

/**
 * Changes the title for the nav menu widget.
 *
 * @param string $title
 * @param string $instance
 * @param string $id_base
 * @return string
 */
function wpse_52108_nav_widget_title_link( $title, $instance = NULL, $id_base="" )
{
    return 'nav_menu' === $id_base ? "<a href="http://example.com">$title</a>" : $title;
}

The $id_base is the first parameter in parent::__construct() in the widget class. For the nav menu widget it is:

parent::__construct( 'nav_menu', __('Custom Menu'), $widget_ops );