This was surprisingly painless for a project that has close to 6KLOC of Python code, probably because I planned for eventual Python 3 support from the start, and the minimal required version of Python 2 is 2.6, which is much more compatible with Python 3 than earlier versions in the 2.x line.
By far the hardest part of this port to Python 3 was porting the construct library on which pyelftools relies for the low-level binary stream parsing. I've forked the construct Github repository to perform the port - it's available here. After construct was ported, it took around 2 hours to port the rest of pyelftools. construct is also being distributed with pyelftools, so there are no actual external dependencies.