Inspired by the answer by Andrej Kesely Instead of adding items one by one I use the update method to ad the entire list at once. I modified the list first using insert and the index where I want to insert it.

from lxml import etree

xml = '<root attr0="val0" attr1="val1" attr3="val3" attr4="val4" attr5="val5"/>'
root = etree.fromstring(xml)

attribs = root.attrib.items()
root.attrib.clear()

attribs.insert(list(dict(attribs).keys()).index("attr3"), ("attr2", "val2"))     
root.attrib.update(attribs)

print(etree.tostring(root))