To be honest, to me the "%" seems the most pythonic way to do it. Format does not seem easier to understand to me . String formatting just cannot be transformed to natural language. I at least don't think "I need to format this string", I think "this variable needs to be in there", in the in there might as well be called "%". I think ["a is %s" % a for a in all_as] just fits.
Although named parameters are nicer with format. In no way should there be a third way to do it. Isn't that the basic principle of Python, to care about things like this? I mean this whole Python 3 problem was to a small extend caused by people rather having an incompatible syntax than two ways to print a string. Going through these troubles and then inflating the language with new syntax for the same thing seems like a waste.