[edit: i thought i had a good demonstration of this. actually, two. but both were wrong. so it does seem to be non-trivial...]
[edit 2: open stack overflow question: http://stackoverflow.com/questions/3545931/efficient-algorit... ]
Now, whether we could come up with such streaming algorithm I'm not sure. I tried solving this problem, and this is what I came up with. Maybe I haven't tried hard enough to go the other route... I guess you could simply slice the incoming stream into a set of chunks, each small enough to make bigin base62 conversion fast (which is square of the size of the chunk), and yet large enough to obscure the occasional loss of space at the chunk boundaries... I guess that would be an option...