If you haven't done that already, you should install the latest Dev Tools (mine are not the latest; they're marked July 2002 but they worked).
- Quit Safari (if running).
- Control click or right click on the Safari icon and choose Show Package Contents.
- Find your way through Contents -> Resources -> English.lproj and open MainMenu.nib
- It will launch Interface Builder and you should have a small window called "MainMenu.nib - Main Menu" with the menu bar.
- Click on History, double click each keyboard shortcut and type your desired key combination for that specific shortcut.
- Close the MainMenu.nib document, save your changes and start Safari.
[Editor's note: Obviously, you could use this same method of changing the other keyboard shortcuts as well. I would recommend working on a backup (or having the Safari installer around), just in case something doesn't work after making your changes.]

