This is from a Ubuntu 12.04 headless build of ffmpeg, also install and tested this using same guide on Ubuntu 13.10. Much of this is based off of ffmpeg build from ffmpeg.org.

sudo apt-get update
sudo apt-get -y install autoconf automake build-essential libass-dev libgpac-dev \
  libsdl1.2-dev libtheora-dev libtool libva-dev libvdpau-dev libvorbis-dev libx11-dev \
  libxext-dev libxfixes-dev pkg-config texi2html zlib1g-dev libfaac0 libfaac-dev
mkdir ~/ffmpeg_sources

yasm

The first step is to compile Yasm which is an assembler used by x264 and FFmpeg. Ubuntu 13.10, Ubuntu 13.04, and Mint 15 users can alternatively install the yasm package from the repository instead of compiling.

cd ~/ffmpeg_sources
wget http://www.tortall.net/projects/yasm/releases/yasm-1.2.0.tar.gz
tar xzvf yasm-1.2.0.tar.gz
cd yasm-1.2.0
./configure --prefix="$HOME/ffmpeg_build" --bindir="$HOME/bin"
make
make install
make distclean
export "PATH=$PATH:$HOME/bin"

x264

H.264 video enprer. See the x264 Encoding Guide for more information and usage examples.

cd ~/ffmpeg_sources
wget http://download.videolan.org/pub/x264/snapshots/last_x264.tar.bz2
tar xjvf last_x264.tar.bz2
cd x264-snapshot*
./configure --prefix="$HOME/ffmpeg_build" --bindir="$HOME/bin" --enable-static
make
make install
make distclean

debian installs:

fdk-aac and opus as of the current install Ubuntu 12.04 LTS there is no packages available, the easiest way (for me) was to just install the .deb packages below.

fdk-aac

Download the correct source for your distro here:
**note this is for AMD64 architecture.. please download the correct deb packages for your specific build
https://launchpad.net/ubuntu/+source/fdk-aac

cd ~/ffmpeg_sources
mkdir fdk-aac
cd fdk-aac
wget -O libfdk-aac0.deb https://launchpad.net/ubuntu/+archive/primary/+files/libfdk-aac0_0.1.1%2B20130514-2_amd64.deb
wget -O libfdk-aac-dev.deb https://launchpad.net/ubuntu/+archive/primary/+files/libfdk-aac-dev_0.1.1%2B20130514-2_amd64.deb
wget -O libfdk-aac0-dbg.deb https://launchpad.net/ubuntu/+archive/primary/+files/libfdk-aac0-dbg_0.1.1%2B20130514-2_amd64.deb
sudo dpkg -i libfdk-aac0.deb
sudo dpkg -i libfdk-aac-dev.deb
sudo dpkg -i libfdk-aac0-dbg.deb

opus

Download the correct source for your distro here:
**note this is for AMD64 architecture.. please download the correct deb packages for your specific build
https://launchpad.net/ubuntu/+source/opus

cd ~/ffmpeg_sources
mkdir opus
cd opus
wget -O libopus0.deb https://launchpad.net/ubuntu/+archive/primary/+files/libopus0_1.0.1-0ubuntu2_amd64.deb
wget -O libopus-dev.deb https://launchpad.net/ubuntu/+archive/primary/+files/libopus-dev_1.0.1-0ubuntu2_amd64.deb
wget -O libopus-dbg.deb https://launchpad.net/ubuntu/+archive/primary/+files/libopus-dbg_1.0.1-0ubuntu2_amd64.deb
sudo dpkg -i libopus0.deb
sudo dpkg -i libopus-dev.deb
sudo dpkg -i libopus-dbg.deb

libmp3lame

MP3 audio enprer.

Most users can install the repository package:

sudo apt-get install libmp3lame-dev

libvpx

VP8/VP9 video enprer and deprer. See the vpx (WebM) Encoding Guide for more information and usage examples.

cd ~/ffmpeg_sources
wget https://webm.googlecode.com/files/libvpx-v1.3.0.tar.bz2
tar xjvf libvpx-v1.3.0.tar.bz2
cd libvpx-v1.3.0
./configure --prefix="$HOME/ffmpeg_build" --disable-examples
make
make install
make clean

libxvid

xVid video enprer and deprer. Popular for streaming services for more information and usage examples.

cd ~/ffmpeg_sources
wget http://downloads.xvid.org/downloads/xvidcore-1.3.2.tar.gz
tar xzvf xvidcore-1.3.2.tar.gz
cd xvidcore
cd build/generic
./configure --prefix="$HOME/ffmpeg_build"
make
make install

ffmpeg

Finally compile and install ffmpeg.. note you will need to rebuild with the prec’s flags enabling it with every rebuild.

cd ~/ffmpeg_sources
wget http://ffmpeg.org/releases/ffmpeg-snapshot.tar.bz2
tar xjvf ffmpeg-snapshot.tar.bz2
cd ffmpeg
PKG_CONFIG_PATH="$HOME/ffmpeg_build/lib/pkgconfig"
export PKG_CONFIG_PATH
./configure --prefix="$HOME/ffmpeg_build" --extra-cflags="-I$HOME/ffmpeg_build/include" \
   --extra-ldflags="-L$HOME/ffmpeg_build/lib" --bindir="$HOME/bin" --extra-libs=-ldl --enable-gpl \
   --enable-libass --enable-libfdk-aac --enable-libmp3lame --enable-libopus --enable-libtheora \
   --enable-libvorbis --enable-libvpx --enable-libxvid --enable-libx264 --enable-nonfree
make
make install
make distclean
hash -r


qt-faststart

qt-faststart ships with FFMPEG. No seprate download is required for it. You can install this after ffmpeg is installed.

cd ~/ffmpeg_sources/ffmpeg/tools
make qt-faststart
cp qt-faststart /usr/local/bin
ldconfig
cd

Thanks to ffmpeg.org for some reference of this guide.