Can I use a catchall address if my mail host doesn't support VERP?
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.

See also How does Civimail reply tracking and forwarding work?

Exim can support VERP routing, even if your mail provider may not be willing to provide this.