Most fast sieves are segmented, so you can get this in efficient amortized time. When you call to get the next segment, you may have to increase the auxiliary prime list, but that's a trivial amount of time. Then you just sieve that segment, exactly how it would be done if you were sieving to some large known upper bound. You can wrap all of that in a next() call. I believe primesieve and primegen both have setups like this. This is also how my forprimes and forcomposites work, as well as my iterator in Perl/ntheory.
This is likely faster than prime-by-prime extensible sieves. I see in the Rosetta Code extensible prime generator task the C solution is a simple segmented generator like I mention above. The first D solution is the rather horrible method you noted. A number of the languages, including Go, implement O'Neill's lazy functional sieve which is more directly what you might be asking for. Ben Tilly shows a lazy sieve using closures in Perl here that should meet your complexity goal.
Of course you can do primality tests, but that takes more time than sieving until your input is large (how large depends on your implementations of both sieve and primality test, but it would certainly be before 10^25).
