Building Vim from the source with the right flags is the general solution.
git clone https://github.com/vim/vim.git
./configure --with-x=yes --disable-gui
The last command will probably raise an error message, which means
you need to install dependencies. Experienced users know how to proceed, but
if it's your first time on this, bad news is there isn't a magic solution,
you need to track down the dependencies with your package manager or
a search engine and keep trying the last line. In Debian and Ubuntu,
apt build-dep vim
will solve a great deal of those.
and if all the dependencies were satisfied, you can finally install it,
but first uninstall your current Vim package, if any. As root,
apt remove vim #for Debian/Ubuntu
See also: Installing Vim help page.