Errors were encountered while processing: mysql-server-5.5 ... E: Sub-process /usr/bin/dpkg returned an error code (1)

start: Job failed to start
invoke-rc.d: initscript mysql, action "start" failed.
dpkg: error processing mysql-server-5.5 (--configure):
subprocess installed post-installation script returned error exit status 1
No apport report written because MaxReports is reached already
Errors were encountered while processing:
mysql-server-5.5
E: Sub-process /usr/bin/dpkg returned an error code (1)

I know you have tried all these solutions that's why you are here but just take a look at once before watching my final solution which is going to work for you.

Solution : 1
Run command

sudo dpkg --configure -a

Solution : 2
Remove and install mysql server again, Run commands :

sudo apt-get --purge remove mysql-server
sudo apt-get install mysql-server

Solution : 3
Remove mysql-server and mysql-server-5.5 package from the file /var/lib/dpkg/status and reconfigure mysql-server

sudo dpkg --configure -a

But you have tried all these solutions and still you are facing same problem, try this Final Solution.
 
Final Solution
Run Command :

sudo apt-get install --reinstall apparmor

Now comment following line in the file /etc/mysql/my.cnf

skip-bdb

Restart mysql

sudo service mysql start

Now your mysql will be started.