How to remap shift-space to underscore in linux (not GNOME or KDE)

I do a lot of shell scripting in linux (running xmonad window manager, so I can use xmodmap or xinput, but not GNOME or KDE control panels), and it would be super useful for a shift-space keystroke to output an underscore ("_") character. Any ideas how to do this?

The following xmodmap expression will map Shift+Space to underscore. Add this to ~/.Xmodmaprc and run xmodmap ~/.Xmodmaprc during startup to make it persistent.

xmodmap -e 'keycode 65 = space underscore space'

Have you been through keymap, loadkeys, etc - http://linux.die.net/man/5/keymaps . It's the same idea but for the kernel and the keyboard driver. You should be able to take your present layout and just add a couple of lines.