How to check if __str__ is implemented by an object

Any object inheriting from the object base will have a __str__ method, so testing if it exists is negligible.

You could store a flag attribute on the object, and test for that instead:

if not getattr(obj, 'has_str_override_flag'):
    override_str_here(obj)
    setattr(obj, 'has_str_override_flag', True)

Since what you want to check is if it has a __str__ implementation that is not the default object.__str__. Therefore, you can do this:

Foo.__str__ is not object.__str__

To check with instantiated objects you need to check on the class:

type(f).__str__ is not object.__str__

This will also work even if Foo doesn't implement __str__ directly, but inherited it from another class than object, which seems to be what you want.