Compiling Vim from source is actually not that difficult. Here's what you should do:
Install all the prerequisite libraries
sudo apt-get install libncurses5-dev libgnome2-dev libgnomeui-dev libgtk2.0-dev libatk1.0-dev libbonoboui2-dev libcairo2-dev libx11-dev libxpm-dev libxt-dev python-dev ruby-dev mercurial
Remove vim if you have it already
sudo apt-get remove vim vim-runtime gvim vim-tiny vim-common vim-gui-common
Compile source code
Download source code
You can get source code here: http://www.vim.org/sources.php
Set Configuration
cd vim ./configure \ --with-features=huge \ --enable-rubyinterp \ --enable-pythoninterp \ --enable-luainterp \ --enable-perlinterp \ --enable-multibyte \ --enable-sniff \ --enable-fontset \ --enable-cscope \ --enable-gui=gtk2 \ --prefix=/usr make VIMRUNTIMEDIR=/usr/share/vim/vim74
Install Vim
sudo make install
If you don't get gvim working (on ubuntu 12.04 LTS), try changing --enable-gui=gtk2 to --enable-gui=gnome2
These configure and make calls assume a Debian-like distro where Vim's runtime files directory is placed in /usr/share/vim/vim74/, which is not Vim's default. Same thing goes for --prefix=/usr in the configure call. Those values may need to be different with a Linux distro that is not based on Debian. In such a case, try to remove the --prefix variable in the configure call and the VIMRUNTIMEDIR in the make call (in other words, go with the defaults).
Besides, if you can't use backspace in Vim, please add following lines to .vimrc
set nocompatible set backspace=indent,eol,start