Sure, Android had NFC payments before, but it was only available to a small percentage of users on Kit Kat, with the proper phone, and it was more technical to use. It wasn't very hard, it just wasn't super easy.
Google had NFC payments long before Kit Kat. The original 2011 method used the Secure Element in either the device or SIM.
Google Wallet is as easy to setup as Apple Pay. Photo input of cards, etc. Moreover, any card works, not just ones where the issuing bank has made a deal to pay Apple.
In fact, The first Apple Pay webpage looked astonishingy similar to Google's Wallet webpage. But of course it would, since modern wallets will have similar functionality.
There are many background differences, but to the user they're quite similar, with the exception of being able to use TouchID on an iPhone instead of entering a PIN at some point, although a PIN and/or signature might still be needed above certain amounts, even with Apple Pay.
I somehow don't see banks developing now different apps for different phones etc. Maybe the credit card provider do that - but I would guess the majority here uses Visa Debit issues by the banks for their checking / current accounts.
For device independence, the banks create payment applets that run in a device's Secure Element, which has a Java runtime.
It's all very similar to how SIM cards work, and in fact was derived from them.
As for the tokenization process, the biggest banks can afford to write their own systems to handle those.
Most other banks, credit unions, etc, instead have to license token services from a toekn service provider. This is why it takes a while for them to get signed up.
For example, Visa and Mastercard have set up such paid token services. So have major third party processors.