glGenerateMipmap takes too long

The GLSL functions ddx() and ddy() can help you determine the amount of blurring you need to do in your shader to make minification as good as with mipmapping. ( to a certain degree )
The trick is calculating the deltas of your uv coordinates of adjacent pixels. The delta depending on the texture size in pixels will give you a blur factor.
A very simple blur implementation will give good results up to approximate 1/4 size.

And yes, with fairly modern GPUs this should be extremely fast.

I think I have the solution. I create the mipmaps an another thread from the original size, upload the whole thing to a single PBO, and in the gl rendering thread these are uploaded one at a time to the individual mipmap levels using the necessary offsets. I only use a maximum four mipmap levels, since the original is not that big, the 1/16 size is only a few pixels in any direction. Rendering is not disrupted by mipmap creation any more. The reason why I am not sure if this was the perfect solution is that I also found a bug in the code that could move the continuously scrolling line of text out of the screen for a moment when a new line was created. Still, creating mipmaps on the fly and in the rendering thread is probably not a good idea and I am happy that I moved as much of this process as I could to another thread. Thanks to everyone for all the tips.