Theora allows changing the bitrate dynamically, here is a patch that implements that
in the GStreamer element. Here is a patch to do it.

Also, here is a small test case, I'm too lazy to write a real unit tests..

import gst

a = gst.parse_launch("videotestsrc is-live=1 ! video/x-raw-yuv, width=640, height=480, framerate=(fraction)30/1 ! theoraenc name=enc bitrate=50  !  appsink name=sink max-buffers=1")

enc = a.get_by_name("enc")
s = a.get_by_name("sink")

a.set_state(gst.STATE_PLAYING)

last = None
avg = None
for i in range(1, 600):
    if i != 0 and i % 60 == 0:
        enc.set_property("bitrate", i)
        avg = None
        print "SET TO ", i
    buf = s.emit("pull-buffer")
    if last and last != buf.timestamp:
        if avg:
            avg = (9*avg/10) +  (100 * 1000 * 8 * buf.size / (buf.timestamp - last))
        else:
            avg =  8 * 1000 * 1000 * buf.size / (buf.timestamp - last)
        print i, avg, buf.size
    last = buf.timestamp