what is the best way to handle subdomains in terms of SEO?
There are no special considerations for subdomains in terms of SEO. Search engines are not interested in domains or subdomains. They are only interested in pages (or, more exactly, URLs).
I am afraid that having lots of 404 error pages will hurt website's SEO.
404s won't cause any problems in terms of SEO. The pages will simply disappear from the search engines' indexes, which is correct (because they contain nothing that will answer a searcher's queries). But 404s are a nuisance for your visitors - and they reflect badly on your site as a whole. If the content of the pages is still relevant, either do as Felgall suggested, or just leave them in place.
I'd also question why you are allowing users to delete entire sections of your site. It doesn't seem like a sensible approach, either for SEO or otherwise.