Our hosting provider does not seem to be able to support VERP on Exim. Is it possible to use a catchall address instead of relying on VERP for bounce processing and forwarding replies
Yes, you can use a catchall mailbox to capture VERP bounces, and CiviCRM will be able to identify VERP data from this.
CiviCRM has two return paths if you enable Reply Tracking, and unless you somehow used separate domains, you won't have two catchall mailboxes. So using a catchall will probably limit your functionality somewhat here.
You could potentially get CiviCRM to poll first for bounces, move unrecognised emails to a "holding" folder in IMAP, then poll that folder for replies on a second pass ... But it is probably easier to just switch to a mail service which supports VERP, since such mailboxes are widely available ... you'd likely save some effort.
Exim can support VERP routing, even if your mail provider may not be willing to provide this.