Voltage sensing using Arduino with and without common reference
the circuit needs to work both when the Ground of the Arduino and the
  Ground of the circuit whose voltage is to be sensed are shorted, and
  when they are not.


I read the above and the only sensible way to achieve this is to design an isolating circuit maybe like this: -



However, given you want a digital number representing your analogue value inside the Arduino I would go for your Arduino controlling an ADC that is isolated via an isolating SPI interface such as: -



The ADuM5401 is key because it also supplies power to the ADC chip. The ADC chip above is typically an AD77xx type device that comes in several flavours from ADI.