After hours of struggling and hundreds time of installing/uninstalling python packages looks like I was able to install python packages including python-minimal. Let me share my success story.

1. At the beginning, I was not even able to uninstall python-minimal. Every time it showed the error I mentioned in my question while installing/uninstalling. Even tried sudo apt-get -f install but without any gain. Somehow I figured out that it can only be uninstalled with few other packages together. Following commands, I used to completed remove python-minimal broken and residual packages:

   
   
   

   sudo apt-get autoremove libpython-stdlib libpython2.7-minimal libpython2.7-stdlib python-minimal python2.7 python2.7-minimal
   
   

   
   
   

   This would remove all the python packages and the softwares which depends on python. I know this was extreme but believe me I was not having any choice.

   
   
   

   sudo apt-get remove --purge $(sudo dpkg -l | egrep "^(rc|iU)" | awk '{print $2}' | tr '
   
   ' ' ')
   
   

   
   
   

   To remove rest of residual and borken packages if any.

   
   
   

   Note: I copied the list of packages which were removed in this step. I knew that I would need it again!




2. Next I searched all the places where python2.7 was installed and removed all files and directory of default python. I wished that I had not to delete them manually but was not having any choice:

   
   
   

   sudo find / -iname python2.7
   
   /etc/python2.7
   
   /usr/local/bin/python2.7
   
   /usr/local/lib/python2.7
   
   /usr/lib/python2.7
   
   /usr/bin/python2.7.13/lib/python2.7
   
   /usr/bin/python2.7.13/bin/python2.7
   
   /usr/bin/python2.7.13/include/python2.7
   
   /usr/bin/python2.7
   
   /usr/include/x86_64-linux-gnu/python2.7
   
   /usr/include/python2.7
   
   /usr/share/doc/python2.7
   
   /usr/share/binfmts/python2.7
   
   /usr/share/lintian/overrides/python2.7
   
   /proc/sys/fs/binfmt_misc/python2.7
   
   /var/lib/binfmts/python2.7
   
   

   
   
   

   I had not to delete all the files/directories listed above and deleted only the default version:

   
   
   

   sudo rm -rf /etc/python2.7 /usr/local/bin/python2.7 /usr/local/lib/python2.7 /usr/lib/python2.7
   
   

   
   
   

   There were other versions of python and were not causing any trouble. I believe the search may vary per user and whereis python command can be used to get the path of default python installed.




3. Next, I installed python with a success:

   
   
   

   sudo apt-get install python
   
   Reading package lists... Done
   
   Building dependency tree       
   
   Reading state information... Done
   
   The following additional packages will be installed:
   
     libpython-stdlib libpython2.7-minimal libpython2.7-stdlib python-minimal python2.7 python2.7-minimal
   
   Suggested packages:
   
     python-doc python-tk python2.7-doc
   
   The following NEW packages will be installed:
   
     libpython-stdlib libpython2.7-minimal libpython2.7-stdlib python python-minimal python2.7 python2.7-minimal
   
   0 upgraded, 7 newly installed, 0 to remove and 21 not upgraded.
   
   Need to get 0 B/3,877 kB of archives.
   
   After this operation, 16.6 MB of additional disk space will be used.
   
   Do you want to continue? [Y/n] y
   
   Selecting previously unselected package libpython2.7-minimal:amd64.
   
   (Reading database ... 250996 files and directories currently installed.)
   
   Preparing to unpack .../libpython2.7-minimal_2.7.12-1ubuntu0~16.04.3_amd64.deb ...
   
   Unpacking libpython2.7-minimal:amd64 (2.7.12-1ubuntu0~16.04.3) ...
   
   Selecting previously unselected package python2.7-minimal.
   
   Preparing to unpack .../python2.7-minimal_2.7.12-1ubuntu0~16.04.3_amd64.deb ...
   
   Unpacking python2.7-minimal (2.7.12-1ubuntu0~16.04.3) ...
   
   Selecting previously unselected package python-minimal.
   
   Preparing to unpack .../python-minimal_2.7.12-1~16.04_amd64.deb ...
   
   Unpacking python-minimal (2.7.12-1~16.04) ...
   
   Selecting previously unselected package libpython2.7-stdlib:amd64.
   
   Preparing to unpack .../libpython2.7-stdlib_2.7.12-1ubuntu0~16.04.3_amd64.deb ...
   
   Unpacking libpython2.7-stdlib:amd64 (2.7.12-1ubuntu0~16.04.3) ...
   
   Selecting previously unselected package python2.7.
   
   Preparing to unpack .../python2.7_2.7.12-1ubuntu0~16.04.3_amd64.deb ...
   
   Unpacking python2.7 (2.7.12-1ubuntu0~16.04.3) ...
   
   Selecting previously unselected package libpython-stdlib:amd64.
   
   Preparing to unpack .../libpython-stdlib_2.7.12-1~16.04_amd64.deb ...
   
   Unpacking libpython-stdlib:amd64 (2.7.12-1~16.04) ...
   
   Processing triggers for man-db (2.7.5-1) ...
   
   Processing triggers for bamfdaemon (0.5.3~bzr0+16.04.20180209-0ubuntu1) ...
   
   Rebuilding /usr/share/applications/bamf-2.index...
   
   Processing triggers for desktop-file-utils (0.22-1ubuntu5.1) ...
   
   Processing triggers for gnome-menus (3.13.3-6ubuntu3.1) ...
   
   Processing triggers for mime-support (3.59ubuntu1) ...
   
   Setting up libpython2.7-minimal:amd64 (2.7.12-1ubuntu0~16.04.3) ...
   
   Setting up python2.7-minimal (2.7.12-1ubuntu0~16.04.3) ...
   
   Linking and byte-compiling packages for runtime python2.7...
   
   Setting up python-minimal (2.7.12-1~16.04) ...
   
   Selecting previously unselected package python.
   
   (Reading database ... 251742 files and directories currently installed.)
   
   Preparing to unpack .../python_2.7.12-1~16.04_amd64.deb ...
   
   Unpacking python (2.7.12-1~16.04) ...
   
   Processing triggers for doc-base (0.10.7) ...
   
   Processing 1 added doc-base file...
   
   Registering documents with scrollkeeper...
   
   Processing triggers for man-db (2.7.5-1) ...
   
   Setting up libpython2.7-stdlib:amd64 (2.7.12-1ubuntu0~16.04.3) ...
   
   Setting up python2.7 (2.7.12-1ubuntu0~16.04.3) ...
   
   Setting up libpython-stdlib:amd64 (2.7.12-1~16.04) ...
   
   Setting up python (2.7.12-1~16.04) ...
   
   

   
   
   

   NOTE: This only installed the very necessary and minimal python packages. You may still need to install all other python packages which were uninstalled in 1st step.

Few Extra Notes:

2nd steps deleted 3rd party python packages as well which were installed globally using pip. Unfortunately, I was not having the list and ended up with few troubles which my projects who need them. But that was not a big deal as all my projects were having their own python requirements.txt file. But still I suggest you all to save the python packages in a file before starting the 1st step. Following command can come in handy:

pip freeze > python_pip_packages.txt

Also I had to delete pip files and directories(similar to how I deleted python default files and directories) and re-installed pip:

sudo apt-get install python-pip  # installing pip

sudo pip install --upgrade pip  # upgrading pip to latest version using pip itself

sudo pip install -r python_pip_packages.txt  # re-installing all 3rd party python packages which were removed in 2nd step.

Hope others don't suffer like me :)