How do I clear cache?
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.