How do I clear cache? On my new site all works fine so far, except that when I try to clear cache (e.g. class cache or table cache or just flush all caches) from the UI. I sometimes get an error about exhausted memory (64M on production, 128M on test site).

Are there any alternatives to clearing cache from the UI? Can I just delete all records from the database tables starting with "cache" and obtain the same result?
You can manually DELETE FROM the cache tables, though doing this with cache_form can result in wonky behavior with people in the middle of form submissions.

However, I suspect the problem isn't with clearing the cache, rather with all of the activity involved in rebuilding everything that gets cached.

Long term, you would be safest to


Disable modules you don't need
Bump up memory_limit for PHP


64M is likely on the low end if you have a lot of modules enabled.  You should really download  the Performance module, enable Summary Logging, run your site for a while, and see where you land on memory stats.  Also note where these go when you clear caches and perform other admin functions.