How do I reimplement (or wrap) a syscall function on Linux?

You can use the wrap feature provided by ld. From man ld:

--wrap symbol Use a wrapper function for symbol. Any undefined reference to symbol will be resolved to __wrap_symbol.

Any undefined reference to __real_symbol will be resolved to symbol.

So you just have to use the prefix __wrap_ for your wrapper function and __real_ when you want to call the real function. A simple example is:

malloc_wrapper.c:

#include <stdio.h>
void *__real_malloc (size_t);

/* This function wraps the real malloc */
void * __wrap_malloc (size_t size)
{
    void *lptr = __real_malloc(size);
    printf("Malloc: %lu bytes @%p\n", size, lptr);
    return lptr;
}

Test application testapp.c:

#include <stdio.h>
#include <stdlib.h>
int main()
{
    free(malloc(1024)); // malloc will resolve to __wrap_malloc
    return 0;
}

Then compile the application:

gcc -c malloc_wrapper.c
gcc -c testapp.c
gcc -Wl,-wrap,malloc testapp.o malloc_wrapper.o -o testapp

The output of the resulting application will be:

$ ./testapp
Malloc: 1024 bytes @0x20d8010

Symbols are resolved by the linker in the order you list them on the command line so if you listed your library before the standard library you'd have precidence. For gcc you'd need to specify

gcc <BLAH> -nodefaultlibs <BLAH BLAH> -lYOUR_LIB <OTHER_LIBS>

This way your libraries would be searched and found first.