This is mainly an excuse to get down some thoughts about the X protocol and how to use it to do these crazy things. Maybe you guys have already figured this stuff out.
As a concrete example, consider the following script:
CapsLock & B::Send, Bacon
In order to make this work properly, we need to block "a" and "b" keypresses from the user, in all cases, from arriving at their destinations. This is fairly easy to do; use XGrabKey. However, our own events will also trigger XGrabKey, and we need to make sure they go through.
So, here's what I have so far:
I saw talk in another issue of using at-spi2 for keyboard events, but I don't think it will get us much in that areas. In particular, I don't think it will allow us to block keyboard events from being delivered when we need to. In any case, these ideas are not mutually exclusive; we can use X to grab keys and get events during passive keyboard grabs, and at-spi2 to get them the rest of the time. Maybe it will provide a way to simulate events without sending them through X, which could help, but I doubt it. (That said, at-spi2 allows for manipulating guis in a lot of other ways, which is awesome.)
Reading through your description, it appears that you know a lot about X11, a lot more than I do, in fact. If you feel that your approach would work then please be my guest and try to implement it. Other than that, there are a few points I'd like to remark upon
So in summary, if you want to retry an approach using X, be my guest. Judging from your plan there's even a good chance you'll succeed. If you run into issues I'll be more than happy to provide assistance.