I would like to communicate with a Galaxy Note 4 (that uses Android HCE to emulate an NFC Forum Type 4 NDEF tag) and an Arduino with a PN532 NFC shield.
As far as I understood, these shields do not support HCE right now. So are there any NFC modules/shields that support Android HCE?
Arduino NFC shields based on NXP's PN532 NFC chip are well suited to work with Android devices in HCE mode. Hence, any such shield would work perfectly fine.
The problem seems to be missing support on the library side.
For instance, the Seeed-Studio library for the PN532 does not provide any means to retrieve the tag type information when performing anti-collision and selection (cf. methods inListPassiveTarget() and readPassiveTargetID()). Hence, it does not allow you to determine if a discovered tag is an ISO/IEC 14443-4 tag (e.g. a HCE device). Nevertheless, once you know that the tag supports ISO/IEC 14443-4, you could easily exchange APDU commands with it using the inDataExchange() method.
Unfortunately, Don Coleman's NDEF library does not currently support NFC Forum Type 4 tags. Hence, if you emulate a Type 4 tag (with NDEF data on it) through HCE, then you would need to manually build the Type 4 tag reader side. How type 4 tags work is defined in the NFC Forum Type 4 Tag Operation specification.