Is it possible to enqueue a script from a widget method (of extended WP_Widget object)?

It’s not true that you have to use wp_localize_script before the wp_head.

Since 3.3 you can use wp_enqueue_script in the body of the document (i.e. in a widget or shortcode callback) and the script is loaded in the footer.

Here’s a skeleton class I’ve used for adding variables for each instance of a widget to an array and then using wp_localize_script to add that entire array to the document. This loads the script, and the variables in the footer.

First register your script on the init hook.

class my_widget extends WP_Widget {

  static $variables=array();

  function my_widget() {
      //initialiser function
  }

  function widget($args, $instance) {   
     //Display widget

     //Then make sure our options will be added in the footer
     add_action('wp_footer', array(__CLASS__, 'add_options_to_script'));

     //Enqueue the script (registered on init)
     wp_enqueue_script( 'my_script');

     //Add the data to the (static) class variable `$variables`, using the widget ID.
     $id = $args['widget_id'];
     self::$variables[$id] = 'my variable for this instance'
   }

   //... irrelevant widget administration functions ...

  function add_options_to_script(){
       //If there is data to add, add it
       if(!empty(self::$widget_cal))
            wp_localize_script( 'my_script', 'my_var', self::$variables);   
  }      

}

  add_action('widgets_init', create_function('', 'return register_widget("my_widget");'));