Find a script called bq27200.sh, designed for battery monitoring. Among other things, it can show you the total charge cycle count since last full reset (which is not easily done by average end user).

For example on my year-plus used phone...

maemo:~# ./bq27200.sh
LOOPMODE=0
Reading values...........................done.

CSOC: 100 % RSOC: 100 %
Average Current: 45 mA
TTF: 0 minutes TTE: 65535 minutes
NAC: 1425 mAh CACD: 1425 mAh CACT: 1425 mAh
SI: 10 mA STTE: 8121 minutes
MLI: 1028 mA MLTTE: 81 minutes
AR: 0 mA ARTTE: 65535 minutes
Last Measured Discharge: 1425 mAh
Cycle Count since Learning: 1 Total Cycle Count since last full reset: 293
Reported Battery Voltage: 4156 mV
Battery Gauge die Temperature: 35 C
Flags: 0xa4
Charge:1 NOACT:0 IMIN:1 CI:0 CALIP:0 VDQ:1 EDV1:0 EDVF: 0
eeprom data:
ILMD=2056 EDVF=3000 EDV1=3248 ISLC=20
DMF=14700 nanoVolt SD=201 thousandths of percent per day
AGELMD=1 TAPER=102 mA
IMLC=1028 mA

Note the 293 charge cycles. On a phone that I bought off eBay with a (credible) month or two's usage, this count was at about 60. Doesn't give you proof positive, but, if the battery chip shows 10 or 20 charges, it's credibly a "new" phone. If it shows 100 or 200 charges, your seller has some explaining to do...