It's an interesting challenge, and I agree one that xinput doesn't appear to be perfectly suited to. I spent some time fiddling around with xmodmap's abilities, and came so frustratingly close to achieving what you want to do... without actually managing to get there.
Using xmodmap, it's possible to assign parenleft as a shifted keysymbol on the left-shift key:
xmodmap -e 'keysym Shift_L = Shift_L parenleft Shift_L parenleft'
which sorta works, at least in testing on my Fedora 17 box, but not in a satisfactory way. I found that, with this mapping in place, the shift key still functioned normally, and didn't render any spurious parens, but (frustratingly) it didn't reliably produce left-parens either. For whatever reason, the key doesn't appear to reliably modify itself, which breaks its shifted assignment... initially. For whatever reason, hitting left-shift a few times in succession would eventually cause it to start producing left-parens, but only after the fourth or fifth press.
One behavior I did notice, however, that you might be able to work with as a "near enough" analogue: I found that after mapping parenleft and parenright onto Shift_L and Shift_R, I could reliably type parens by "rolling" across both shift keys — in other words, with this mapping:
xmodmap -e 'keysym Shift_L = Shift_L parenleft Shift_L parenleft'
xmodmap -e 'keysym Shift_R = Shift_R parenright Shift_R parenright'
pressing Shift_L followed by Shift_R, then releasing both, would output a right-paren, or a left-paren in the other direction. (The paren mappings could be reversed, of course; I couldn't quite decide which way felt more "natural".)
That was as close as I came to achieving the exact behavior you're looking for; it doesn't seem like it's possible using xmodmap alone.
I was halfway-convinced that it simply isn't possible, period, but then I realized that there's at least one key which functions exactly as you describe: The Super ("Windows") key. Under Gnome Shell, it's a modifier key (mod4), which produces a different effect (triggering Overview) when pressed alone. So, at least in theory, it may be possible to implement your desired shift-key overloading in the same manner.
...But, I have absolutely no idea how that would be done, or how invasive it would be to get bogged down in the necessary processing every time you hit the Shift key. :-)