You need to avoid devices with rolling shutters. In practice, that means using something with a CMOS sensor rather than a CCD (and then testing before purchase). For the actual device, if small size is important you could check out sites that review helmet/handlebar cams and similar devices. Otherwise, there's a huge range of very small videocameras on the market now.
Edit for clarification: almost all, or maybe all, CCD devices use a rolling shutter. The majority of consumer-level CMOS devices also use a rolling shutter, but a large minority don't. You need to pick something from the "large minority" category.
Edit for correctness: as pointed out by Mark1234 further down, I'm generally correct apart from being exactly wrong
. Swap all references to CCD and CMOS. Put it down to brainfarts.