Add a new file ~/.gtkrc-2.0, write the following line in it:

gtk-can-change-accels = 1


Source this file and open a Gnome application such as evince. Move cursor to the menu item you want to change accelerate key for. Hang over it and press the accelerate key. It will be set. Then modify the ~/.gtkrc-2.0 file and change the value from 1 to 0 to disable it. Then the new accelerate key stays there. So sweet.