@stephdl
I think i got it finally. Thoiugh i managed to access the database thanks to this post, i did a mistake again of course, and forgot that semicolon when ran SHOW DATABASES. I deleted the database using this. 
Went through the package uninstall and removal as described above. Rebooted the server, just in case and ran the installation again, but the same error: Not Found.
I noticed that the folder /usr/share/wordpress got recreated, but it contains only a tmp folder. Running a search for wordpress i found another folder /etc/wordpress/ which contains only wp-config.php.
Any hints?