Why can't it be a regular press? Maybe one with a direct to press imaging drums and in-line coaters? Would be cheaper than digital (like an Indigo) for cost per impression.
(And 4over does do runs that large... you just gotta place multiple orders. They'll even group the shipping for you too. I'm looking right now and they will do a run of 100k, then you can just to a run of 50k... plus all of February, you get double points!)
It doesn't have to be digital however by going digital you remove the need to pay for plates, negatives, extra setup, etc.
I have a customer who needs large quantity printing of brochures and rack cards like 150,000 4 over doesn't do large custom orders so Im not sure who to get these from.