There is an obscure setting that is for this. XFCE has it in the GUI, but Gnome/Unity does not. The feature is an obscure one that's turned off by default, and perhaps because so few people use it, it doesn't always work very well.
But give it a try anyway. You'll need to install gconf-editor, if you haven't already:
sudo apt-get install gconf-editor
If you go into gconf-editor and do a search (ctrl+f) for "can_change_accels". In the dialog, make sure and check the "Search also in key names" checkbox. You should see a result with something like /desktop/gnome/interface/can_change_accels.
Check that to True.
Once that's enabled, you can configure shortcuts by clicking on a menu and hovering your mouse over an item. When the menu item you want to bind a shortcut key to is hovered over, type the shortcut. It should appear immediately.
There are some caveats. One is, I'm not sure this works with Unity's global menu bar. Since I don't use Unity, I can't test and make sure. Another caveat is that non-native Gnome apps probably won't do this. So for example, if you're running a Java app, don't expect this to work.