In the meantime, I gave up and decided to configure FTP to work around the problem.
While doing that it turned out that wordpress is actually trying to find files under /srv directory (??!) and not under /var/www as I previously assumed, which looks like this:
#:/srv/www/wp-content/localhost$ ls -l
drwxrwxr-- 2 www-data www-data 4096 Dec 2 15:58 blogs.dir
lrwxrwxrwx 1 www-data www-data 39 Dec 2 15:58 languages -> /var/lib/wordpress/wp- content/languages
lrwxrwxrwx 1 www-data www-data 37 Dec 2 15:58 plugins -> /var/lib/wordpress/wp-content/plugins
lrwxrwxrwx 1 www-data www-data 36 Dec 2 15:58 themes -> /var/lib/wordpress/wp-content/themes
drwxrwxr-x 3 www-data www-data 4096 Dec 3 13:20 upgrade
drwxrwxr-- 3 www-data www-data 4096 Dec 2 17:53 uploads
Except that user:group was set to root:root for all. Same was for everything under /var/lib/wordpress.
As soon as I changed permissions everywhere to www-data:www-data, things started to work without FTP.
Now the problem was that if I, say, install a theme automatically, the theme cannot be properly activated. It turns out it installs in the wrong place:
#:/var/lib/wordpress/wp-content/themes$ ls -l
lrwxrwxrwx 1 www-data www-data 48 Dec 3 12:11 index.php -> /usr/share/wordpress/wp-content/themes/index.php
drwxr-xr-x 7 www-data www-data 4096 Dec 3 13:38 montezuma
drwxr-xr-x 8 www-data www-data 4096 Dec 3 13:22 responsive
lrwxrwxrwx 1 www-data www-data 51 Dec 3 12:11 twentyeleven -> /usr/share/wordpress/wp-content/themes/twentyeleven
lrwxrwxrwx 1 www-data www-data 48 Dec 3 12:11 twentyten -> /usr/share/wordpress/wp-content/themes/twentyten
drwxr-xr-x 6 www-data www-data 4096 Dec 3 13:37 twentytwelve
So I have to manually go to /srv/www/wp-content and move those montezuma, responsive and twentytwelve above to /usr/share/wordpress and link back with ln -s. Pain in the ass.
Basically the only solution that I found was to not use the apt-get method of installing wordpress, but just do this:
sudo unlink wordpress
sudo wget http://wordpress.org/latest.tar.gz
sudo tar xvfz latest.tar.gz
Now everything works just as expected. Final solution - install wordpress manually and not from Ubuntu repository.