I don’t think you can do this from XAML, for exactly the reasons you describe.
I ended up doing it in the code-behind. Although it’s code, it’s only a single line of code, and still rather declarative, so I can live with it. However, I’d really hope that this is solved in the next version of WPF.
Here’s a sample line of code from one of my projects:
this.InputBindings.Add(new KeyBinding(
((MedicContext)this.DataContext).SynchronizeCommand,
new KeyGesture(Key.F9)));
SynchronizeCommand in this case is an instance of RelayCommand, and (obviously) F9 triggers it.