I wonder if it is even possible to provide this type of exchanger service without registering a company (of any kind, even if it was offshore).
To receive and send money you will need a merchant account and to get a merchant account you will need to be fully KYCed. In most cases (I have not seen any merchant yet) merchant requires company information to open an account with them.
for every fiat exchange, a bank is required. can the whole business be done as a physical person (no company) and do banks tolerate such things?
It's only possible when dealing with cash in person which is of course inconvenient considering the time we are in. No one is okay with cash in hand.
OMG. You don't know how does it work in Russia. And these exchangers are Russian. Have you heard about darks? Have you heard about merchants registered to other person's name you can buy? Have you heard about Qiwi payment system? You can register there using darks and have a merchant (providing only physical person's passport number). Also you can have Qiwi virtual card and receive money from clients to this card. And almost all exchangers that provide exchanges from bank cards accept funds to Qiwi virtual cards.