Yes it's very possible to do this. Without seeking support it's trivial, just instruct the encoder to encode with a low bitrate for a few seconds and then increase it.

To support seeking you could encode a low bitrate stream, and a high quality stream, and then a number of ramps between these. So when you seek you start with the low bitrate stream and then after a few time units go on the ramp to the high quality stream.