venv é um script de conveniência para criar envs virtuais, mas não substitui totalmente tudo o que virtualenv pode fazer. Usar qualquer um é bom para a maioria dos casos. virtualenv não está obsoleto.
python3 -m venv funciona após a instalação de python3-venv porque o Debian remove alguns scripts do pacote Python básico. python3-virtualenv não coloca o script virtualenv em seu caminho por algum motivo, mas python-virtualenv faz isso e funcionará bem para qualquer versão.
Não é importante para qual versão virtualenv está instalada, ele pode produzir envs para qualquer versão instalada passando -p pythonX (onde X é a versão). venv , sendo mais simples, criará apenas envs da versão da qual é executado, e só está disponível desde 3.3.
$ sudo apt-get install python-virtualenv
$ virtualenv -p python3 env
$ source ./env/bin/activate
$ sudo apt-get install python3-venv
$ python3 -m venv env
$ source ./env/bin/activate