You can define custom translations keysym for some terminal emulators. I've done this in urxvt in order to free up C-j and C-S-[letter] combinations for my own use.
urxvt will allow you to translate the Shift_L keycode into "(" or "()" or "i_love_hacker_news_<3". And it still does it's job as a modifier too. The only problem is that "i_love_hacker_news<3" will be output as soon as the press event is received, so you'll output "(" even when you press shift as part of a chord.
You can write perl scripts in urxvt that can capture X keyboard events, and maybe your script could only output "(" if it detects that no intermediate X event was detected between the press and the release of "(".
I'm not totally sure that you get THAT much info from urxvt, but it's the best approach that I know of. As an alternative, maybe you could write a program to intercept X events before they reach the terminal (and/or any other program).
That's about as far as I care to go right now.
Let me know if you get something working, I'd be interested in using it too.
This is from memory, so bear with me if its not perfect, but I setup xmodmap with
keysym 50 = Shift_L parenleft Shift_L keysym 62 = Shift_R parenright Shift_R
Xmodmap allows you to define multiple symbols for a key. The first symbol is what you get with no modifiers; the second is with shift; the third is with Mode_switch (or AltGr, depending) and the fourth is with Shift and AltGr. There's sometimes although a 5-8, but that varies by platform and I haven't done enough experiments to really nail down what those are for linux these days, OR if those are tied to mod1/mod2/etc. instead of shift/altgr/mode_switch or specific modifiers like that.
Anyway, all the keysyms always defined the first three anyway (no modifiers, shift, and Mode_switch) and some defined the fourth. I don't have or use a Mode_switch key (yet) but I may try that out as a 'Greek' key or such, but since 90% of the time I'm programming I'm not sure if I'd ever use it.
My lines above defines parenleft as the symbol to send if key 50 (the left shift key) is pressed while the shift modifier is active. So, I can use the right shift to turn on the shift modifier, and then left shift turns into a left parenthesis key. Similarily, I can use the left shift key to turn the right shift into a right parenthesis.
So, to type a pair of parenthesis back to back "()" I press right shift, press left shift, release right shift, and tap right shift. It's certainly more awkward than what Steve was able to setup, but hey, its where I've got so far.