Se você compilar o ffmpeg a partir do código fonte, você poderá incluir o suporte a libx264 em sua configuração de compilação. Você pode compilar a biblioteca você mesmo (como recomendado pelo FFmpeg) ou instalar o pacote libx264-dev para obter os cabeçalhos que você precisa.
Como alternativa, você pode baixar um binário pré-compilado de um dos links no site. Eu usei aqueles por um tempo, e acho que eles incluem libx264.
Em relação ao problema do avconv, há uma guerra santa entre os dois projetos, e o mantenedor do pacote que faz a maioria dos pacotes para o Debian (e, portanto, o Ubuntu e, portanto, o Mint) está no lado da libav. O ffmpeg nos repositórios é um avconv re-marcado também. EDIT: ou então eu ouvi.
EDIT2: Você pode encontrar a maioria dos downloads e informações relevantes no link