Vim autocomplete for Python

Try Jedi! There's a Vim plugin at https://github.com/davidhalter/jedi-vim.

It works just much better than anything else for Python in Vim. It even has support for renaming, goto, etc. The best part is probably that it really tries to understand your code (decorators, generators, etc. Just look at the feature list).

This can be a good option if you want python completion as well as other languages. https://github.com/Valloric/YouCompleteMe

The python completion is jedi based same as jedi-vim.

As pointed out by in the comments, this answers is outdated. youcompleteme now supports python3 and jedi-vim no longer breaks the undo history.

Original answer below.

AFAIK there are three options, each with its disadvantages:

1. youcompleteme: unfriendly to install, but works nice if you manage to get it working. However python3 is not supported.
2. jedi-vim: coolest name, but breaks your undo history.
3. python-mode does a lot more the autocomplete: folding, syntax checking, highlighting. Personally I prefer scripts that do 1 thing well, as they are easier to manage (and replace). Differently from the two other options, it uses rope instead of jedi for autocompletion.

Python 3 and undo history (gundo!) are a must for me, so options 1 and 2 are out.