Install homebrew in Ubuntu 14.04
It says that you need these packages:
sudo apt-get install build-essential curl git m4 ruby texinfo libbz2-dev libcurl4-openssl-dev libexpat-dev libncurses-dev zlib1g-dev
So, installing the above packages will solve your issue.
Since Feb 2018, you install linuxbrew (=homebrew for linux) just by:
sudo apt install linuxbrew-wrapper