What can be done, if anything, to tune a SharePoint database? SharePoint uses a single table (i.e. dbo.AllUserData) with columns like nvarchar1, nvarchar2, ..., nvarchar64 or int1, int2, ..., int16 (193 columns altogether) to store all items from all lists in all site collections.


Can creating new indexes, recomputing statistics, etc. help?
Let's forget for now that it very likely to lose Microsoft support for SharePoint installation modified like this.
Am I right in thinking that such a design makes all classic databases tuning techniques useless?
Has anyone ever tried to solve performance problems of SharePoint in any other way than adding more/faster hardware?
There is not a lot you can do to tune the database it self.  You aren't allowed to create indexes, or statistics.  

Keep your content databases small.  If they get to 100 Gigs you'll want to add another content database (there's ways to do this through the SharePoint UI).

As the tables grow you will want to be sure that you are doing index rebuilds and updating stats regularly.

You can look at using the EBS feature if you are using SharePoint 2010 (might be in SharePoint 2007 as well) which will allow you to move the blob data out of the database and store it on the file system using SQL Server's FILESTREAM feature.

Short of that there isn't much you can do besides throwing more hardware at the problem.