I deprecated the class and the test class both and tried installing my package into a professional edition, but was not able to do it. It resulted in the same error as before : missing feature : apex classes.
So, no, deprecating will not solve your problem.
The only way to do it is to delete the class from your org (after having managed package component deletion enabled)
No, because deprecated code isn't deleted code, it's simply flagged as "do not use." However, once you pass the security review, you'll be able to install your package in Professional Edition orgs, even though they can't normally have Apex Code in their orgs.