Thanks to @ErykSun the solution:

Python code

string1 = "my string 1"
string2 = "my string 2"

# create byte objects from the strings
b_string1 = string1.encode('utf-8')
b_string2 = string2.encode('utf-8')

# send strings to c function
my_c_function.argtypes = [ctypes.c_char_p, ctypes.c_char_p]
my_c_function(b_string1, b_string2)

I use this in my code:

POINTER(POINTER(c_char))

But I think both are equivalent.

Edit: Actually they are not http://docs.python.org/2/library/ctypes.html#ctypes.c_char_p

ctypes.c_char_p Represents the C char * datatype when it points to a zero-terminated string. For a general character pointer that may also point to binary data, POINTER(c_char) must be used. The constructor accepts an integer address, or a string.

So POINTER(POINTER(c_char)) is for binary data, and POINTER(c_char_p) is a pointer to a C null-terminated string.

c_char_p is a subclass of _SimpleCData, with _type_ == 'z'. The __init__ method calls the type's setfunc, which for simple type 'z' is z_set.

In Python 2, the z_set function (2.7.7) is written to handle both str and unicode strings. Prior to Python 3, str is an 8-bit string. CPython 2.x str internally uses a C null-terminated string (i.e. an array of bytes terminated by \0), for which z_set can call PyString_AS_STRING (i.e. get a pointer to the internal buffer of the str object). A unicode string needs to first be encoded to a byte string. z_set handles this encoding automatically and keeps a reference to the encoded string in the _objects attribute.

>>> c = u'spam'
>>> a = c_char_p(c)
>>> a._objects
'spam'
>>> type(a._objects)
<type 'str'>

On Windows, the default ctypes string encoding is 'mbcs', with error handling set to 'ignore'. On all other platforms the default encoding is 'ascii', with 'strict' error handling. To modify the default, call ctypes.set_conversion_mode. For example, set_conversion_mode('utf-8', 'strict').

In Python 3, the z_set function (3.4.1) does not automatically convert str (now Unicode) to bytes. The paradigm shifted in Python 3 to strictly divide character strings from binary data. The ctypes default conversions were removed, as was the function set_conversion_mode. You have to pass c_char_p a bytes object (e.g. b'spam' or 'spam'.encode('utf-8')). In CPython 3.x, z_set calls the C-API function PyBytes_AsString to get a pointer to the internal buffer of the bytes object.

Note that if the C function modifies the string, then you need to instead use create_string_buffer to create a c_char array. Look for a parameter to be typed as const to know that it's safe to use c_char_p.

The following code works:

test.py:

import ctypes
lib = ctypes.CDLL("./libtest.so")
string_buffers = [ctypes.create_string_buffer(8) for i in range(4)]
pointers = (ctypes.c_char_p*4)(*map(ctypes.addressof, string_buffers))
lib.test(pointers)
results = [s.value for s in string_buffers]
print results

test.c (compiled to libtest.so with gcc test.c -o libtest.so -shared -fPIC):

#include <string.h>
void test(char **strings) {
    strcpy(strings[0],"this");
    strcpy(strings[1],"is");
    strcpy(strings[2],"a");
    strcpy(strings[3],"test!");
}

As Aya said, you should make sure there is room for the terminating zero. But I think your main problem was that the string buffer was garbage collected or something similar, as there was no direct reference to it anymore. Or something else is causing trouble in the creation process of the string buffers when no references are stored for them. For example this results in four times the same address instead of different addresses:

import ctypes
pointers = [ctypes.addressof(ctypes.create_string_buffer(8)) for i in range(4)]
print pointers