Miklos and Tom,
one option may be to merge the work that Miklos described with gr-trellis (or the other way around :-))
Recall there was a discussion in the recent past of volk-ing the basic trellis algorithms such as VA and SISO.
I believe the work that Miklos describes would be a wonderful way to start.
Also, Miklos, some of the functionality you are describing (interleaving, generation of codes, FSM structure, etc) is in gr-trellis.