It's both. If it doesn't work with threads, there is no concurrency.
If the threads have to stop, it's still concurrency in the sense that threads are stopped in arbitrary places (just like an interrupt can stop a task at any point in its execution and dispatch another task or whatever).
But the garbage collector isn't running concurrently with the threads.
I.e. I think the term "concurrent garbage collector" is understood to be in contrast with "stop-the-world garbage collector" not with "synchronous garbage collector as a library function in a single-threaded virtual machine".
So when you say "real GC, not reference counting", you have to understand that tracing GC and reference counting are duals, and every concurrent collector is going to be some hybrid of the two [1].
But there are a number of algorithms that most people would probably consider "real GC" that don't stop the world. Modern Java GCs use the train algorithm [2], which bounds pause times to some arbitrarily-sized constant. Erlang per-process heaps [3] also give good soft-real-time characteristics.
It is theoretically possible to run the whole GC in a background thread (eg. while a GUI is idle). Both the JVM and the CLR have options for this [4][5], but they're only useful for workloads with large pause times (eg. GUI apps, lightly-loaded servers) and so aren't enabled by default.
