Control-Up,Down,Left,Right as extra keys
From my /etc/personal-linux-console.map:
# Up
control keycode 103 = F69
# Left
control keycode 105 = F71
...
string F69 = "\033<Cu>"
string F71 = "\033<Cl>"
From my /etc/rc.local:
loadkeys -q /etc/personal-linux-console.map
I just chose these values arbitrarily. Now in the Linux console, Control-Up will send the five characters Escape-<-C-u->, and so on. You tell readline how you want to interpret that in your ~/.inputrc file.
With X, there are various places to tweak things. Some changes you can do with xmodmap. Depending on how you start X, you might be able to just save your xmodmap commands in ~/.Xmodmap or /etc/X11/Xmodmap and have them automatically loaded. Some changes will be too tricky for xmodmap, and you'll need to write XKB definition files (these reside under /usr/share/X11/xkb on my machine). These are very hairy and poorly documented. You should find what few docs and tutorials there are by Googling. In about a year we should see a new generation of XKB deployed, so I don't know how much sense it makes to invest time in learning the old format.
I don't know whether it's possible to do Control-keys with xmodmaps commands. I think it is. I used to have mine in custom XKB files (I needed the XKB files anyway, for some stuff.) Now I have the control keys configured in my X terminal (urxvt)'s config files. I use the same arbitrarily chosen sequence escape-<-C-u-> for control-up, and so on, so that I can use the settings in my .inputrc file (for readline) and for other terminal programs (mutt, elinks, and so on).
For some key redefinitions, it's also useful to write your own terminfo files so that terminfo-aware applications will be more likely to be able to handle/recognize them. I don't do that for my Control-arrow settings though. But for instance, if you have some key defined to output the string Escape-<-S-U->, you may want to use a terminfo file that declares that string as being the "Undo" key. Then in some applications you'll be able to just refer to that key as "Undo", no matter what it says on your physical keyboard.
It's complex. There's no general solution that's simpler. (Though if you were only concerned with a few keys, in a few applications, you may well be able to ignore some of the complexity.)