Just confirmed that signals is not a viable option. Is too slow, as Antonie already pointed. It's almost 5 times slower than with SIGEV_THREAD. 

The problem now is:

If I use Py_AddPendingCall, the tests can hang sometimes. I can still follow Amaury suggestion tough.

If I try to acquire the GIL PyGILState_Ensure() call PyObject_CallObject and release the GIL in the aio_completion_handler function a SEGFAULT occurs in 2.7.3 but not in 3.3 and newer..

This branch works only on 3.3 and newer: https://github.com/felipecruz/pyaio/tree/feature/check_no_pending_call

This other branch will segfault 2.7.3 with just acquire and release GIL on the completion handler:
https://github.com/felipecruz/pyaio/tree/feature/py27_gil_error

Since this looks very strange, can someone confirm this behavior?

Tested on a Ubuntu12 64.