I have patched (see attachment) Python 2.7.4 (as available for download at python.org/download) to disable initialization of Unicode (an embeded system requirement) and now it segfaults with the following program:

    #include <Python.h>
    
    int main(int argc, char** argv)
    {
      int i;
      Py_NoSiteFlag = 1;
    
      Py_SetProgramName(argv[0]);
    
      for (i = 0; i < 3; i++)
      {
        printf("run no. %d\n", i);
    
        Py_Initialize();
        Py_Finalize();
      }
    
      return 0;
    }

The problem appears to be related with the reference count of the empty tuple. I've also applied the following patch in Objects/tupleobject.c to help diagnose the problem:

    @@ -928,6 +928,8 @@ PyTuple_Fini(void)
     #if PyTuple_MAXSAVESIZE > 0
         /* empty tuples are used all over the place and applications may
          * rely on the fact that an empty tuple is a singleton. */
    +    printf("free_list[0]->ob_refcnt before XDECREF: %d\n",
    +        free_list[0]->ob_refcnt);
         Py_XDECREF(free_list[0]);
         free_list[0] = NULL;

*Without* the patch for Python/pythonrun.c the program produces the following results under Ubuntu 13.04 x64:

    run no. 0
    free_list[0]->ob_refcnt before XDECREF: 58
    run no. 1
    free_list[0]->ob_refcnt before XDECREF: 57
    run no. 2
    free_list[0]->ob_refcnt before XDECREF: 57

Note the strange ref count of the empty tuple (free_list[0]). Now, *with* the patch, the application will not hold so many references to the empty tuple and the finalization code ends up trying to deallocate it (what, from my limited understading of the code, is not supposed to happen):

    run no. 0
    free_list[0]->ob_refcnt before XDECREF: 2
    run no. 1
    free_list[0]->ob_refcnt before XDECREF: 1
    Segmentation fault (core dumped)

The actual patch I'm using is much more complicated. This is just the minimal patch able to reproduce the problem. I tried undefining Py_USING_UNICODE but then the build doesn't succeed.