It has been a while since I asked this question but it looks like a lot of people are looking at it. I ended up using a behavior which connects the VM command list to the FrameworkElement. This seems to be the most flexible and resusable solution.
public class AttachCommandBindingsBehavior : Behavior<FrameworkElement>
{
    public ObservableCollection<CommandBinding> CommandBindings
    {
        get
        {
            return (ObservableCollection<CommandBinding>)GetValue(CommandBindingsProperty);
        }
        set
        {
            SetValue(CommandBindingsProperty, value);
        }
    }
    public static readonly DependencyProperty CommandBindingsProperty = DependencyProperty.Register("CommandBindings", typeof(ObservableCollection<CommandBinding>), typeof(AttachCommandBindingsBehavior), new PropertyMetadata(null, OnCommandBindingsChanged));
    private static void OnCommandBindingsChanged(DependencyObject sender, DependencyPropertyChangedEventArgs e)
    {
        AttachCommandBindingsBehavior attachCommandBindingsBehavior = (AttachCommandBindingsBehavior)sender;
        if (attachCommandBindingsBehavior == null)
            return;
        ObservableCollection<CommandBinding> commandBindings = (ObservableCollection<CommandBinding>)e.NewValue;
        if (commandBindings != null)
        {
            if (attachCommandBindingsBehavior.CommandBindings != null)
                attachCommandBindingsBehavior.CommandBindings.CollectionChanged -= attachCommandBindingsBehavior.CommandBindings_CollectionChanged;
            attachCommandBindingsBehavior.CommandBindings.CollectionChanged += attachCommandBindingsBehavior.CommandBindings_CollectionChanged;
        }
    }
    void CommandBindings_CollectionChanged(object sender, System.Collections.Specialized.NotifyCollectionChangedEventArgs e)
    {
        ObservableCollection<CommandBinding> collection = (ObservableCollection<CommandBinding>)sender;
        if (collection != null)
        {
            foreach (CommandBinding commandBinding in collection)
                AssociatedObject.CommandBindings.Add(commandBinding);
        }
    }
}
In xaml you can then do this:
<i:Interaction.Behaviors>
    <localBehaviors:AttachCommandBindingsBehavior CommandBindings="{Binding CommandBindings}"/>
</i:Interaction.Behaviors>