How can I handle WPF routed commands in my ViewModel without code-behind?

I would rephrase the question as:

How can I handle WPF routed commands in my ViewModel without code-behind?

To which, I would respond: Great Question!

WPF does not provide a built-in way to do this, which is especially annoying when you're first starting WPF and everybody tells you that "Code-Behind is evil" (it really is). So you have to build it yourself.

Building it Ourselves

So, how do go about creating such functionality ourselves? Well, first we need an equivalent of a CommandBinding:

/// <summary>
///  Allows associated a routed command with a non-routed command.  Used by
///  <see cref="RoutedCommandHandlers"/>.
/// </summary>
public class RoutedCommandHandler : Freezable
{
  public static readonly DependencyProperty CommandProperty = DependencyProperty.Register(
    "Command",
    typeof(ICommand),
    typeof(RoutedCommandHandler),
    new PropertyMetadata(default(ICommand)));

  /// <summary> The command that should be executed when the RoutedCommand fires. </summary>
  public ICommand Command
  {
    get { return (ICommand)GetValue(CommandProperty); }
    set { SetValue(CommandProperty, value); }
  }

  /// <summary> The command that triggers <see cref="ICommand"/>. </summary>
  public ICommand RoutedCommand { get; set; }

  /// <inheritdoc />
  protected override Freezable CreateInstanceCore()
  {
    return new RoutedCommandHandler();
  }

  /// <summary>
  ///  Register this handler to respond to the registered RoutedCommand for the
  ///  given element.
  /// </summary>
  /// <param name="owner"> The element for which we should register the command
  ///  binding for the current routed command. </param>
  internal void Register(FrameworkElement owner)
  {
    var binding = new CommandBinding(RoutedCommand, HandleExecuted, HandleCanExecute);
    owner.CommandBindings.Add(binding);
  }

  /// <summary> Proxy to the current Command.CanExecute(object). </summary>
  private void HandleCanExecute(object sender, CanExecuteRoutedEventArgs e)
  {
    e.CanExecute = Command?.CanExecute(e.Parameter) == true;
    e.Handled = true;
  }

  /// <summary> Proxy to the current Command.Execute(object). </summary>
  private void HandleExecuted(object sender, ExecutedRoutedEventArgs e)
  {
    Command?.Execute(e.Parameter);
    e.Handled = true;
  }
}

And then we need a class that will actually associated the RoutedCommandHandler with a specific element. For this, we'll make a collection of RoutedCommandHandlers as an attached property, like so:

/// <summary>
///  Holds a collection of <see cref="RoutedCommandHandler"/> that should be
///  turned into CommandBindings.
/// </summary>
public class RoutedCommandHandlers : FreezableCollection<RoutedCommandHandler>
{
  /// <summary>
  ///  Hide this from WPF so that it's forced to go through
  ///  <see cref="GetCommands"/> and we can auto-create the collection
  ///  if it doesn't already exist.  This isn't strictly necessary but it makes
  ///  the XAML much nicer.
  /// </summary>
  private static readonly DependencyProperty CommandsProperty = DependencyProperty.RegisterAttached(
    "CommandsPrivate",
    typeof(RoutedCommandHandlers),
    typeof(RoutedCommandHandlers),
    new PropertyMetadata(default(RoutedCommandHandlers)));

  /// <summary>
  ///  Gets the collection of RoutedCommandHandler for a given element, creating
  ///  it if it doesn't already exist.
  /// </summary>
  public static RoutedCommandHandlers GetCommands(FrameworkElement element)
  {
    RoutedCommandHandlers handlers = (RoutedCommandHandlers)element.GetValue(CommandsProperty);
    if (handlers == null)
    {
      handlers = new RoutedCommandHandlers(element);
      element.SetValue(CommandsProperty, handlers);
    }

    return handlers;
  }

  private readonly FrameworkElement _owner;

  /// <summary> Each collection is tied to a specific element. </summary>
  /// <param name="owner"> The element for which this collection is created. </param>
  public RoutedCommandHandlers(FrameworkElement owner)
  {
    _owner = owner;

    // because we auto-create the collection, we don't know when items will be
    // added.  So, we observe ourself for changes manually. 
    var self = (INotifyCollectionChanged)this;
    self.CollectionChanged += (sender, args) =>
                              {
                                // note this does not handle deletions, that's left as an exercise for the
                                // reader, but most of the time, that's not needed! 
                                ((RoutedCommandHandlers)sender).HandleAdditions(args.NewItems);
                              };
  }

  /// <summary> Invoked when new items are added to the collection. </summary>
  /// <param name="newItems"> The new items that were added. </param>
  private void HandleAdditions(IList newItems)
  {
    if (newItems == null)
      return;

    foreach (RoutedCommandHandler routedHandler in newItems)
    {
      routedHandler.Register(_owner);
    }
  }

  /// <inheritdoc />
  protected override Freezable CreateInstanceCore()
  {
    return new RoutedCommandHandlers(_owner);
  }
}

Then, it's as simple as using the classes on our element:

<local:RoutedCommandHandlers.Commands>
  <local:RoutedCommandHandler RoutedCommand="Help" Command="{Binding TheCommand}" />
</local:RoutedCommandHandlers.Commands>

Interaction.Behavior implementation

Knowing the above, you might then ask:

Wow, that's great, but that's a lot of code. I'm using Expression Behaviors already, so is there a way to simplify this a bit?

To which, I would respond: Great Question!

If you're already using Interaction.Behaviors, then you can use the following implementation instead:

/// <summary>
///  Allows associated a routed command with a non-ordinary command. 
/// </summary>
public class RoutedCommandBinding : Behavior<FrameworkElement>
{
  public static readonly DependencyProperty CommandProperty = DependencyProperty.Register(
    "Command",
    typeof(ICommand),
    typeof(RoutedCommandBinding),
    new PropertyMetadata(default(ICommand)));

  /// <summary> The command that should be executed when the RoutedCommand fires. </summary>
  public ICommand Command
  {
    get { return (ICommand)GetValue(CommandProperty); }
    set { SetValue(CommandProperty, value); }
  }

  /// <summary> The command that triggers <see cref="ICommand"/>. </summary>
  public ICommand RoutedCommand { get; set; }

  protected override void OnAttached()
  {
    base.OnAttached();

    var binding = new CommandBinding(RoutedCommand, HandleExecuted, HandleCanExecute);
    AssociatedObject.CommandBindings.Add(binding);
  }

  /// <summary> Proxy to the current Command.CanExecute(object). </summary>
  private void HandleCanExecute(object sender, CanExecuteRoutedEventArgs e)
  {
    e.CanExecute = Command?.CanExecute(e.Parameter) == true;
    e.Handled = true;
  }

  /// <summary> Proxy to the current Command.Execute(object). </summary>
  private void HandleExecuted(object sender, ExecutedRoutedEventArgs e)
  {
    Command?.Execute(e.Parameter);
    e.Handled = true;
  }
}

With the corresponding XAML:

<i:Interaction.Behaviors>
  <local:RoutedCommandBinding RoutedCommand="Help" Command="{Binding TheCommand}" />
</i:Interaction.Behaviors>

The accepted answer is very nice, but it seems the OP didn't quite understand how RoutedCommands work and that caused some confusion. Quoting from the question:

When a routed command is defined in a ViewModel as a RelayCommand (or DelegateCommand), it is easy to bind directly to the command like this: Command={Binding MyViewModelDefinedCommand}.

This is ambigous, but either way it's incorrect:

1. Either - one can't define a RoutedCommand as a Relay/DelegateCommand because RoutedCommand is a different implementation of ICommand interface.
2. Or - if a VM exposes an actual RoutedCommand, one will still face the same issue as with those RoutedCommands that are defined outside of VM (because of the way RoutedCommands work).

RoutedCommand is a specific implementation of ICommand

RoutedCommand's Execute/CanExecute methods do not contain our application logic (when you instantiate a RoutedCommand, you don't pass Execute/CanExecute delegates). They raise routed events which, like other routed events, traverse the element tree. These events (PreviewCanExecute, CanExecute, PreviewExecuted, Executed) are looking for element that has CommandBinding for that RoutedCommand. CommandBinding object has event handlers for those events, and that is where our application logic goes (now it's clear why exposing a RoutedCommand from your VM doesn't solve the issue).

// The command could be declared as a resource in xaml, or it could be one 
// of predefined ApplicationCommands
public static class MyCommands {
    public static readonly RoutedCommand FooTheBar = new RoutedCommand();
}

xaml:

<Window x:Class...
        xmlns:cmd="clr-namespace:MyCommands.Namespace">
    <Window.CommandBindings>
        <CommandBinding Command="{x:Static cmd:MyCommands.FooTheBar}"
                        Executed="BarFooing_Executed"/>
    </Window.CommandBindings>

<Grid>
...
// When command is executed, event goes up the element tree, and when
// it finds CommandBinding on the Window, attached handler is executed
<Button Command="{x:Static cmd:MyCommands.FooTheBar}"
        Content="MyButton"/>
...
</Grid>
</Window>

CommandBinding object

CommandBinding class does not inherit from DependencyObject (it's Command property can't be bound to a command exposed on VM). You can use event handlers attached to a CommandBinding to forward the call (in code-behind) to the VM - there is nothing important there, no logic (nothing to test). If you want no code-behind, then the accepted answer has nice solution (does that forwarding for you).