You can still use Composer with PSR-0 or classmap.
I'd probably go with the classmap first. Advantages: Can deal with multiple classes per file. Can deal with arbitrary file structures.
Once you achieved using Composer's autoloading, you can start removing either the existing autoloader or those require_once/include_once
that are likely spread all over the place.
Once you've got rid of all that file loading legacy and have established Composer autoloading, you can try to organize the code according to PSR-0. This will probably require you to rename files and reposition them. It might also be the case that the classes don't have any identifiable prefixes - which is bad for your PSR-0 autoloading because all these files would belong into one single folder.
Note that until this point you haven't changed the name of any class, so the code should run without any changes.
Using namespaces does not have a very noticeable advantage. You'd be forced to rename all classes, rename all usages of that class name, and all in all it won't provide any noticeable benefit if used alone.
On the other hand, you sound like you do want to refactor everything else as well, so switching to namespaces can be used as a signal for "newer" code.
You can use PSR-4 and PSR-0 at the same time, so it won't affect your renaming of classes (besides the necessary class name changes in all the places).