I work in a tire shop, and a large part of my job is fixing flat tires. I'd say that 90% of the things we pull out of tires are nails or screws, 7% are some other metal object, and the remaining 3% are the interesting things like wood, rocks, or tools. My favorites so far have been:
A pair of wirecutters that were in such good condition we kept them and use them in the shop
One of those small co2 canisters for airsoft guns and small paintball guns
A set of keys... there had to be 10 keys on the ring, and one of them punctured the tire and stayed in long enough to get to our shop - never did find the owner
Some piece of bone... it looked like a deer leg bone, but thats just a guess
And my personal favorite? A 9mm FMJ pistol round. The riced out eclipse pulled in right before closing, telling us a 'deal' had gone bad, and that some guy shot at them. I didn't believe it, but as we pieced the story together, we found a hole through the bumper, a hole through the tire, and a dent in the alloy wheel where the bullet finally stopped. The round was still inside the tire. I patched it for free, it was just such a good story.