Bit of an odd request, but really any decent business class firewall should be able to permit custom NAT rules so that network A's clients are source NAT'ed as a different IP as network B's clients.
If you're getting a routed subnet(s) from the ISP, then you'll need to configure proxy ARP or "virtual IPs" on the outside interface to "answer" or masquerade for requests to/from one of these subnets that are now getting routed to your firewall/router.
Can the public IPs be contiguous or do they have to appear to be different? If the former is ok, just ask the ISP for static /29 (5 IPs) and save yourself some configuration grief. You can then light up a virtual IP on the WAN interface and writing a NAT rule for network B should be pretty straightforward.
EDIT:
Haven't confirmed, but it appears as though the business/decision maker of company A doesn't want any liability of company B's web surfing habits.
If that's the case, the best solution is to get an entirely different Internet connection registered as company B. Solves the different IP problem, and in reality, affords better "CYA" protection than a routed subnet registered under the same business.