This implements a new builtin, abstractmethod, which when used as a method decorator declares the method to be abstract, causing the class to be abstract (i.e. it cannot be instantiated).  A subclass of an abstract class is still abstract unless it overrides all abstract base methods.

Here's a version that compiles with C89 (GCC 2.96) and doesn't leak the 'fast' object.
File Added: abstract.diff

Perhaps this is a better question for the PEP rather than the impl, but can attributes be abstract?

class Foo:
  abstract_override_me = ???

If so, then __isabstractmethod__ might be better named as:  __isabstract__.  I think this might work:

class Abstract:
  __isabstractmethod__ = True

class Foo:
  abstract_override_me = Abstract()

Do you want arbitrary objects to be able to declare their abstractness or should the impl also check that an attribute is callable?

check_new_abstracts() should return a Py_ssize_t since it returns the size of a container (set).  The return value is already captured in a Py_ssize_t, so it's just the signature (and prototype) that should change.

PySet_Add()s return value isn't checked in check_new_abstracts().  It might be nice to factor out the common code between the two new functions into a static helper function.  That would get rid of the PySet_Add problem.

By calling: PyObject_GetAttrString(meth, "__isabstractmethod__"), that means a new string object is allocated and then thrown away with each call.  This could be improved by creating an interned string for "__isabstractmethod__".  (I realize this is only when types are created which shouldn't be too often.)

Neil: The intention is that only methods can be abstract.  I don't think we should attempt to only check the __isabstractmethod__ attribute for objects that we know are methods; that would be an expensive check to make (you'd have to call __get__ if it exists) and since this is a __magic__ attribute, you void your warrantee if you mess with it. :-)

In this version (v3), I've fixed the C nits and done the refactoring you suggested, and also added an optimization: check_abstracts() returns immediately if the base class doesn't have the ABSTRACT flag set.
File Added: abstract.diff

Something like this was submitted quite a while ago.