All above methods failed for me and then I found that I was not changing AllowOverride None to AllowOverride All in my virtual host file at /etc/apache2/sites-available/default
<VirtualHost *:80>
ServerAdmin webmaster@localhost
DocumentRoot /var/www
<Directory />
Options FollowSymLinks
AllowOverride All <---- replace None with All
</Directory>
<Directory /var/www >
Options Indexes FollowSymLinks MultiViews
AllowOverride All <--- replace None with All
Order allow,deny
allow from all
</Directory>
...