Can the 3MB apex limit be increased?

Yes. I have worked with Orgs where this limit has been increased. Raise a case with SF support.
A few have had it increased to 6MB
I am sure if you explain the steps that you have taken (cleaning up the code and checking for test methods) then this will aid your case.

As per Salesforce Summer ’18 Release Note (preview), Apex Code Size Limit has been increased.

The maximum amount of Apex code that you can use in an org has been doubled, from 3 MB to 6 MB. If your org was previously approved for an increase above 6 MB, it remains unchanged.

Where: This change applies to Lightning Experience and Salesforce Classic in Enterprise, Performance, Unlimited, and Developer editions.

https://releasenotes.docs.salesforce.com/en-us/summer18/release-notes/rn_apex_code_size_limit.htm