Is it possible to determine whether a purchased phone has a new battery?
If the battery is user replaceable, you can check the production number on that and try to decode battery date. I don't know if the manufacturer numbering scheme is standardised or if the app can be trusted to decipher, so I would suggest the alternative below. 
Edit  Accubattery Pro gives you an indication of estimated Vs actual capacity . I have no idea how accurate it is but surely can be indicative
A reliable indicator is the battery capacity, since capacity reduces with age. A battery, even if not used loses it's capacity to hold charge, significantly, over a period of time. You can refer to question for details
How to determine maximum capacity of a battery in mAh? - received fake battery
If device is rooted, you can check if information here helps  /sys/class/power_supply/battery/