Allow two classes of apps in the App Store: those approved by Apple and those not approved by Apple. The unapproved apps would only be accessed through direct searches (they would not appear in top 10 lists or be featured on the front page), would carry cigarette-grade warnings that it might kill your phone and cause cancer, and maybe Apple would take a slightly larger cut to incentivize developers to get apps approved. Non-approved apps could still be pulled from the store by Apple at any point for blatant violations of Apple's guidelines. That way, if developers want to skirt around all the headaches of Apple's approval process and if users want to gamble on an app to run on their own hardware that Apple won't or can't approve in a timely fashion, they can.
Not that Apple would ever do such a thing.