python3 --version returns python 2.7 after messing up with environments

Question

I was trying to create a new python virtual environment and I run sudo virtualenv xxx and I might try other similar comments too. After that, my python3 is messed up. You can see the output of the related comments:

$ python --version
Python 2.7.12
$ python3 --version
Python 2.7.12
$ python3.5 --version
Python 2.7.12
$ which python3
/usr/bin/python3
$ which python3.5
/usr/bin/python3.5
$ ls -lh /usr/bin/python*
lrwxrwxrwx 1 root root    9 Nov 24  2017 /usr/bin/python -> python2.7
lrwxrwxrwx 1 root root   16 Nov 24  2017 /usr/bin/python-config -> python2.7-config
lrwxrwxrwx 1 root root    9 Nov 24  2017 /usr/bin/python2 -> python2.7
lrwxrwxrwx 1 root root   16 Nov 24  2017 /usr/bin/python2-config -> python2.7-config
-rwxr-xr-x 1 root root  319 Feb 24  2016 /usr/bin/python2-jsonschema
-rwxr-xr-x 1 root root  151 Nov 23  2015 /usr/bin/python2-pbr
-rwxr-xr-x 1 root root 3.4M Dec  4  2017 /usr/bin/python2.7
lrwxrwxrwx 1 root root   33 Dec  4  2017 /usr/bin/python2.7-config -> x86_64-linux-gnu-python2.7-config
lrwxrwxrwx 1 root root    9 May 26  2017 /usr/bin/python3 -> python3.5
lrwxrwxrwx 1 root root   16 Mar 23  2016 /usr/bin/python3-config -> python3.5-config
-rwxr-xr-x 2 root root 3.4M Jun 23 17:37 /usr/bin/python3.5
lrwxrwxrwx 1 root root   33 Nov 28  2017 /usr/bin/python3.5-config -> x86_64-linux-gnu-python3.5-config
-rwxr-xr-x 2 root root 3.4M Jun 23 17:37 /usr/bin/python3.5m
lrwxrwxrwx 1 root root   34 Nov 28  2017 /usr/bin/python3.5m-config -> x86_64-linux-gnu-python3.5m-config
lrwxrwxrwx 1 root root   10 May 26  2017 /usr/bin/python3m -> python3.5m
lrwxrwxrwx 1 root root   17 Mar 23  2016 /usr/bin/python3m-config -> python3.5m-config

And also since the python3 is broken, lsb_release is also broken which uses python3:

$ lsb_release -a
  File "/usr/bin/lsb_release", line 64
    print("No LSB modules are available.", file=sys.stderr)
                                               ^
SyntaxError: invalid syntax

And since lsb_release is broken, I have a hard time with apt.

I tried to reinstall python3 but it does not allow me since I am in a corporate network:

$ sudo apt-get install --reinstall python3.5
The following additional packages will be installed:
  libpython3.5 libpython3.5-dev libpython3.5-minimal libpython3.5-stdlib python3.5-dev python3.5-minimal
Suggested packages:
  python3.5-venv python3.5-doc binfmt-support
The following packages will be upgraded:
  libpython3.5 libpython3.5-dev libpython3.5-minimal libpython3.5-stdlib python3.5 python3.5-dev python3.5-minimal
7 upgraded, 0 newly installed, 0 to remove and 307 not upgraded.
Need to get 43.5 MB of archives.
After this operation, 5120 B disk space will be freed.
Do you want to continue? [Y/n] y
...<just trimming for easy reading>
E: Failed fo fetch <some network internal address> 403 Forbidden
E: Failed fo fetch <some network internal address> 403 Forbidden
E: Failed fo fetch <some network internal address> 403 Forbidden
E: Unable to fetch some archives, maybe run apt-get update or try with --fix-missing?

I tried to add ppa:deadsnakes/ppa to bypass this internal network thing and I got this result:

$ sudo add-apt-repository ppa:deadsnakes/ppa
  File "/usr/bin/lsb_release", line 64
    print("No LSB modules are available.", file=sys.stderr)
                                               ^
SyntaxError: invalid syntax
Traceback (most recent call last):
  File "/usr/bin/add-apt-repository", line 22, in <module>
    sys.stdout.detach(), encoding="UTF-8", line_buffering=True)
AttributeError: 'file' object has no attribute 'detach'

So, it seems like binary files of python3 and python2 are the same, and I cannot install python3 from apt due to both network limitations and the chicken egg thing of ubuntu, you need python to install python.

I really need help, and reinstalling ubuntu from scratch is not an option at all, unfortunately.

I appreciate any help. Thank you!

Possible related articles:

python3 points to python2.7.6

https://www.linuxquestions.org/questions/ubuntu-63/python3-v-returns-python-2-7-12-can%27t-get-python3-to-work-4175650241/

https://askubuntu.com/questions/853377/error-with-lsb-release-a-in-ubuntu-16-04-xenial

https://forums.linuxmint.com/viewtopic.php?t=245836

ps: OS is Ubuntu 16.04, but this problem is not OS dependent, and it is possible to recreate it with other versions too.