Should I use a current limiting resistor for pins labeled as NC which should not be left floating?
Take a look at Microchip's application note AN1484, entitled "Recommended Usage of Microchip 23XX512/23XX1024 Serial SRAM Devices"

On page 4, it says this:


  Pin 3 – SIO2 (available on 23AXXX and 23LCXXX devices) is used for SQI
  mode of operation. As this is an input pin, this should not be left
  floating. This pin may be connected to either VSS or VCC. It is
  recommended that this pin be connected to VCC in the event that the
  device enters SQI mode, as this pin will need to be high to exit SQI.
  For the 23LCVXXX devices, pin 3 is internally tied high, so can be
  treated as a true No Connect.


For example, Figure 1 from the app note shows the recommended connections for SPI operation:



In your case, the upper schematic is appropriate (23LC512 has no VBAT support), so pin 3 should be tied to VCC via a 10K resistor. The lower figure is for 23LCV512, in which case it can be left floating.