Hmm, looks like the sendkey.c thing might work. Although the documentation on XTestFakeKeyEvent() specifically says "This extension is not intended to support general journaling and playback of user actions", which is what (I think) I want. I wonder why the disclaimer.
XInput2 and XIGrabKeycode should provide the highest priority grabbing under Xorg so that even applications that do server-wide grabs (e.g. games) will be bypassed.
XTest was meant for automated UI testing but can be used for all sorts of automated behaviors.
For the first part i wrote a simple program[2] years a go that uses xkill to kill the toplevel window with Ctrl+Alt+K (mainly for games that grab the input and hang) which can be used as a quick example. I haven't tried to use XTestFakeKeyEvent but there seems to be a lot of code out there which can be used as an example, e.g. this one[2] (see the send_key function near the top).
[0] https://linux.die.net/man/3/xigrabkeycode
[1] https://linux.die.net/man/3/xtestfakekeyevent
[2] http://runtimeterror.com/tools/xkeyller/
[3] http://git.yoctoproject.org/cgit.cgi/matchbox-history/plain/...