For US stocks, transfer agents are involved in the transaction process.
As stock shares represent various rights and privileges, like voting rights and dividends, someone needs to keep track of who owns what shares. While it can be done within the issuing company, handling ownership & proxy voting is usual outsourced to a stock transfer company like Computershare or AST.
With those transfer agents the owner would either have a book only entry or a ledger entry with physical (paper) shares in their possession. Realize that physical shares was not uncommon as it is today in order to avoid the high brokerage fees prior to the 1990s.
In the US if you are holding the shares directly (book or physical), a Medallion Signature Guarantee is required for transfer. Should you have physical shares, the seller/buyer would submit those shares to the transfer agent along with the required tax information of the new owner.
As to the share price of the transaction that would be a matter between the two parties unless other fiduciary concerns are imposed. Note that while the transfer agent may not care that a $200 a share stock was transferred for $1 per share, the IRS might, and I believe the price per share has to be declared.
So while the exchange isn't involved, some entity like the transfer agent needs to be so that proper ownership of shares is recorded and that proxy voting material and dividends are assigned.
From my answer to Can shares be trades outside of an exchange? but the other answer regarding National Best Bid Offer (NBBO) is relevant as well.
