Uhm...in my case I don't think it's the same issue. For some reason I can't strafe backwards; this is, the combination of backpedal+strafe works, but it doesn't get any more input, so I can't jump.
It does seem like the same issue. Snag is, shift also modifies keycodes. The only usable modifier key is [Alt]; as an experiment, you could try binding [Alt] to +attack ("fire" in some other engine), and activate "always run" (+speed in the console for regular Quake; running will be on until -speed is issued). With a couple keys bound to +strafeleft/right, and a non-modifier key bound to "jump", the layout should allow jumping too.
The working layout is: [Z], [X] - strafe left/right; [Alt] - +attack; cursor arrows - move forward/backward, turn left/right; [A] - jump.
I thought it was a limitation of my keyboard...
No, it's a limitation of either SDL, X, Linux keyboard driver, or Quake source itself, either of which can't recognise/filter key scancodes modified with [Control] and [Shift]. [Alt]-modified keycodes seem to be filtered correctly though.