"Complex sampling" can break Nyquist?
Your understanding is correct. If you sample at rate $f_s$, then with real samples only, you can unambiguously represent frequency content in the region $[0, \frac{f_s}{2})$ (although the caveat that allows bandpass sampling still applies). No additional information can be held in the other half of the spectrum when the samples are real, because real signals exhibit conjugate symmetry in the frequency domain; if your signal is real and you know its spectrum from $0$ to $\frac{f_s}{2}$, then you can trivially conclude what the other half of its spectrum is.

There is no such restriction for complex signals, so a complex signal sampled at rate $f_s$ can unambiguously contain content from $-\frac{f_s}{2}$ to $\frac{f_s}{2}$ (for a total bandwidth of $f_s$). As you noted, however, there's not an inherent efficiency improvement to be made here, as each complex sample contains two components (real and imaginary), so while you require half as many samples, each requires twice the amount of data storage, which cancels out any immediate benefit. Complex signals are often used in signal processing, however, where you have problems that map well to that structure (such as in quadrature communications systems).