This is really an extended comment.

I think that it's unlikely that an unconditional result of this type is known, because your problem is not all that different from the problem of finding a prime in the desired interval.  For fixed $c$, the number of positive integers less than or equal to $x^c$ with no prime factor less than $x$ is asymptotic to
$$c\cdot\omega(c){x \over \log x}$$
where $\omega$ is the <a href="https://en.wikipedia.org/wiki/Buchstab_function">Buchstab function</a>. In other words the density of the numbers you're interested in is only larger than the density of primes by a constant factor, so it would be rather surprising to me if one of them could be found much more efficiently than a prime could be.  Of course this is not a proof and one could imagine a "formula" such as $n!+1$ that always yields a composite, but this seems a bit too much to hope for.

Also I'm not sure I understand your suggested weakening of the upper bound to $q < n^{O(n^\epsilon)}$. If $q$ is that large, then it takes something like $n^\epsilon \log n$ bits just to write it down, and that can't be done in polylog time.  I suppose you could allow $q$ to be expressed using some "formula" that is more compact than binary representation, but in that case, very few numbers of that size are going to be expressible by a short formula.