If we could find a number co-prime to $2^n!$ in $n^{O(1)}$ time, or even just a number divisible by at least one prime greater than $2^n$, we could factor it to find such a prime.  This would constitute a solution to the [strong conjecture with factoring](http://michaelnielsen.org/polymath1/index.php?title=Finding_primes), so it is an open problem.

As far as I know, it is open whether or not it is possible to find a prime larger than $2^n$ in time $2^{\frac{n}{2}+o(1)}$ with or without a factoring oracle.  The finding primes page doesn't say this explicitly but I don't see any obvious method to beat this using a factoring oracle from the information presented.  Perhaps someone can confirm that this weaker problem is open.