apt-get - Segmentation fault: Error Processing package libc-bin

While segmentation faults are normally associated with poorly written code attempting to access a restricted area of memory, I don't believe that's the cause of your issue. While it's not as common these faults can also be caused by misbehaving hardware. I would begin by ensuring that you have a stable environment by running memtest on your system and ensuring that your hdd is in good shape if you are using swap. If you discover faulty hardware, replace it.

Can't stat

means that the file or directory either doesn't exist or your user doesn't have access to it even via sudo. You can check permissions via the ls -l /lib/i686-linux-gnu command. Since there is no /usr/lib/i686-linux-gnu that I can find in a 64-bit version of Ubuntu (assumed based on Path /usr/lib/x86_64-linux-gnu given more than once ).

My best assessment based on the information you've provided is that the root cause to several of these errors is improper entries in your software sources. These are found in the /etc/apt/sources.lst file or the lists in the /etc/apt/sources.list.d directory. You might begin trying to clean it up with How can PPAs be removed?

If you are running a desktop with GUI, you might prefer Y PPA Manager which is a helpful tool for such tasks.

If there's anything confusing or unclear about this answer, please leave a comment and I'll do my best to clarify.

EDIT: Further assessment to cover additional points raised since this answer was originally written.

7) In the absence of faulty hardware we'll need to dig a bit deeper

8) abundantly clear since point 5.

9) Also clear since point 4.

Re-EDIT10) having a valid /etc/apt/sources.list means you don't need to replace it.

11) I have a system which was also upgraded from 14.04 to 16.04, my /etc/apt/sources.list is still intact as you now report your is.

12) That appears possible based on the bug mentioned by dessert in this comment.

At this point, the options are limited. Here they are in no particular order. Feel free to pick the one that seems least painful.

1) Revert to a previous backup

2) Backup user data (you should be doing this anyway) and install from scratch

3) Fix your installation. Download apt and all it's dependencies and reinstall them all with dpkg -i packagename