Just use standard PKI. It's secure, it's easy and it's standard.
Create a key pair for each customer. The private key is protected by a pass phrase (also known as a PIN code). Distribute the key pairs along with the bank's public key on a chip which does the encryption/signing.
Now go the the ATM or POS. Enter the card with the chip. Unlock the private key with the PIN. Let the card encrypt a message to the bank using the bank's public key and signed by the customers private key.
It's not rocket science. And to the end user it works exactly the same as before. It's cheap too.