bash:./helloworld_s:no existe tal archivo o directorio. El archivo está claramente allí.

Como se explica en el error de redhat #868662, la forma recomendada de vincular es dejar que gcc llame a ld como se muestra a continuación;

> gcc -nostartfiles helloworld-lib.o -o helloworld_s -lc

Lo que da como resultado una vinculación correcta;

> ldd helloworld_s
        linux-vdso.so.1 =>  (0x00007ffd283bf000)
        libc.so.6 => /lib64/libc.so.6 (0x00007fd011b62000)
        /lib64/ld-linux-x86-64.so.2 (0x00007fd011f2f000)

Y la ejecución va bien;

> ./helloworld_s
Hello, world!

¿Por qué ld vincula a /lib/ld64.so.1 que no existe?
Porque esta es la configuración predeterminada para un sistema genérico, no solo para Linux.