millis() should be pretty accurate. delay() is NOT very accurate.
time = millis();
delay(1000);
Serial.println(millis() - time);
// That should give you 1000 (or 1001) every time.
Hmm. Don't forget that Serial.print() is unbuffered and takes close to 1ms per byte at 9600bps...
The originally posted prints the time that is the sum of times used by delay(1000), Serial.println(), and "lots of code." I'd expect that to be greater than 1000 for each loop()...