Yes, as long as they weren't banned Pokemon to begin with. So no Ho-Oh, Luigia, Celebi or Deoxys (there was a period in 2006 where it was given away at Space Center Houston).
Also, I believe Bottle Caps ARE a permanent increase to stats, but they leave the IVs alone. I assume it was done that way so you couldn't just Bottle Cap a Ditto and breed, and also for Hidden Power.