Soryr to hear your having issues with your Yubikey Neo. Whilst not one of our products, they are a very convenient form of authentication.

In answer to your questions :

It appears that like all phones, the S4 has a "sweetspot" where NFC detection and reading is at its best. It does however appear that the S4's spot is quite narrow :


Best to check the Yubikey forums.

Any NFC device will be affected and possible detuned by localised metalic objects, keys and keyrings included.

Embedded in the battery.

Worth a shot !