Is there an efficient test for if an NFA accepts a subset of another NFA?
The problem of deciding language containment in NFAs is $PSPACE$-complete. To prove this, it is easy to reduce from the universaility problem for NFAs (testing whether $L(A)=\Sigma^*$)
So, in a way, you have to determinize, but you may do so on-the-fly. 

Your observation about co-NP is wrong (but nice). Such a witness can indeed be checked in polynomial time in the witness, but the shortest witness itself may be exponential in the length of the input. Since $PSPACE=co-PSPACE$, then deciding non-containment is also $PSPACE$-complete.

To state things more carefully, deciding whether $L(A)\subseteq L(B)$ is $PSPACE$ in the size of $B$ (since only $B$ needs to be complemented), and $NLOGSPACE$ in the size of $A$.