I struggled with this a little bit today, but ended up with a solution that seems not so bad after all. I did a quick write up of it here . . .
https://ben.fogbutter.com/2016/02/20/testing-multiple-python-versions-on-circleci.html
I hope this works for others as well!