When a user is removed from my Google Workspace domain, is his data still available in the on-premises backup?

Yes, the deleted user’s data is always safe in the local backup.

Restore to another Google Workspace account

You can safely restore (merge) all the Google Workspace data for this user to another user. For example, if an employee is leaving your company, his Google Workspace data can be merged with the employee who is responsible for taking over his job. Detailed instructions can be found at Tutorial: How to transfer Google Workspace data from one account to another.