clang_complete просто ожидает, что clang будет установлен в вашей системе. Установите последнюю версию или скомпилируйте ее из svn и все. Если вы хотите использовать опцию libclang, которая намного быстрее, вам понадобятся python и VIM с включенным python.