I've managed to obtain several objects, which __getattribute__ cannot be applied to them.

Minimal non-working example (a more detailed one is attached):
b = abs.__class__
b.__getattribute__(b, 'x')

Proxying such objects turned out to be even harder that proxying everything else in Python (as if it wasn't already mindbogglingly hard).

As you can see, given that 'builtin_function_or_method' object you can obtain its __getattribute__, but you cannot apply it.

Tested with Python 3.5.2 and 3.6.0b1.

What's the deal with that broken __getattribute__? It seems to be specific to 'builtin_function_or_method' class, but why is it broken? If it is "PyObject_GenericGetAttr", then why object.__getattribute__(b, 'x') works? What am I missing?

Hmm.  It's not clear what you're after here.  The error from your example code is correct.  The valid invocation is:

b.__getattribute__(abs, 'x')

That works just fine.  If you want to look up *class* attributes then you must call __getattribute__ on the class's class:

type(b).__getattribute__(b, 'x')

This is how attribute lookup works.  I recommend closing this as not-a-bug.  If you have further question your best bet is to ask on the python-list mailing list.

Oh, I see. The invocation b.__getattribute__(b, attrname) worked on so many objects that I didn't even think it could be incorrect.

Sorry for wasting your time.