Except this is exactly how Android Pay and
  Apple Pay work: they store the billing
  information on the client side.

No, Apple Pay does not. And I'm pretty sure neither does Android Pay. What Apple Pay does is produce encrypted tokens based on the account holder's information and the device(s) authorized to use it. It is only this encrypted token which is stored on a client device and it is verified on each transaction as well as periodically replaced by the servers.

The PAN and related data is stored securely on Apple's servers (or, more likely, PCI compliant servers provided by Paymentech). This is why merchants have to accept these payment methods specifically and not treat them as "regular" card-not-present transactions.