I'd go for the decorator approach for its explicitness. It reads like plain English without having a deeper understanding of the concepts. Also, it does not pollute the implementors namespace. Even if one argues for the naming convention solution, one has to admit that it causes confusion for most people stumbling over it for the first time.

I think these are all equally good. The Impl's name should never need to be referred to, so ultimately the choice should be based on what's easiest to read.

EDIT: actually, your examples wouldn't work as-is, since it would result in circular references (something Python isn't well-equipped to handle). Your target names would need to be strings instead of the actual class.

EDIT2: I have updated the code to allow for another syntax:

    class AnyImplNameIWant(MyTrait, metaclass=Impl, target="MyStruct"):
        ...

It would certainly be nicer if `MyStruct` didn't need to be a string of course. I really think these options are mostly down to taste, so I'll just have to trust that this alternative reads sufficiently more nicely.

Correction: what's easiest to read to someone who hasn't carefully read every single line of your library. Verbosity is not always bad, if it yields clarity.