If you want more features (and something more up to date than whats in the apt packages), you have to compile it yourself.
You say you are on Debian, and all these should work on that platform.
You will first want to clone the repo and remove any existing vim installations.
git clone https://github.com/vim/vim.git
sudo apt-get remove --purge vim*
Next, you want to install the headers that you will need for a basic vim installation. This might not be a comprehensive list, but it works for me. If you get errors in the compilation you should be able to find what packages you still need via a quick google search.
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
Next, you want to install the headers for any features you are planning to use. Here, I am using python, ruby, and perl.
sudo apt-get install python-dev ruby-dev libperl-dev
Next, cd into your directory:
Run the following commands:
Now, you need to select what features you want. You can look at the makefile source for more information about how to do this. To see a list of available features, you can look at feature.h. I suggest setting the options like I do below instead of manually messing with comments in the makefile and feature.h. I feel it makes it easier to change your configuration. It's worth noting that features=huge should include both the clipboard and xterm=clipboard features.
Run this command:
Next, simply do a:
sudo make install
And you should be good to go, assuming there are no errors.