Can the police track my Iphone 4S if it was completely brand new and never been turned on?

No, it is not possible for anyone to do this. You would have had to configure it, enable "Find my iPhone", and have it turned on.

Even then the police will do nothing that you cannot do on your own.

Ouch. Sorry.

most likely not

It it a stolen iPhone?

The police has other things to do than tracking you, unless...

Since you didn't even unpacked it. I think it's gone for good. Sorry for your lost.

Still you can report lost to the police with your receipt.

Lost or Stolen

http://support.apple.com/kb/HT2526