A simple thing that is actually being done: ATMs pulling in the card with a randomly changing speed. This makes it very hard for the skimmer to get a reliable reading. The actual reading by the ATM is done during the second phase, inside the ATM.
The speed just has to be fairly constant within a single swipe - then you can adjust for it. It usually is when humans do that - human hand has quite an inertia.
The security feature on ATMs makes it vary wildly within a single swipe.
As an example, this was largely the case with transactions not involving PINs (signed-for purchases). Recent introduction of EMV (chip-and-pin cards) was really done to shift responsibility for such transactions back onto the customers and reduce banks' losses.
This is also the case with stolen cards (in the UK and Ireland, at least): losses related to such cases are covered by the bank, even for losses occurring before the card was reported stolen. This is the reason banks implement various pattern-matching techniques to try and detect such transactions as soon as possible.
The smartcard mechanism hopefully uses some challenge-response setup that makes it impossible to read out by scammers. (aside from the difficulty of interfacing with the chip during the split second it's in the right position)
Thinking a bit further, perhaps it would be possible to create some fake information on the magnet stripe that would identify anybody who uses it as a thief?
There are concerns over the cryptographic integrity of PIN codes in some chip and pin implementations, but it's a much harder target for ATM skimmers, which is why organized criminals have switched to tampering with retail EPOS terminals instead. And the threshold for that is a lot higher, too. (http://www.telegraph.co.uk/news/worldnews/asia/pakistan/3173...) Overall, the level of card crime in the UK seems to have diminished significantly since the switchover, although the general rule applies: if you build a better safe, you'll attract a better class of safe-cracker.
Could an OTP generator like RSA SecurID do the trick? Let's say you enter two memorized numbers and then the last two numbers on the fob to make the four digit PIN (you would not want the whole PIN to be on the fob). Bonus: you need to use it for web logon as well.
Some customers will pay extra for such services. Potentially avoiding hassles like ATM fraud and identity theft in the first place is worth a small fee per month to me because of the massive timesuck that could take place if they happened.
What could be done given that the fundamental use of an ATM machine (put in card, type in PIN) can't be changed overnight?
On machines capable of displaying pictures, users could be shown what the insertion slot ought to look like so they could compare.
A shroud could be placed over the keypad to reduce the viewing angles available to a pinhole camera.
Could smart phones be used to provide a "have something" security model? Let's say you paid $0.25 less per ATM transaction if you used your bank's iPhone app to generate a unique pin for every visit.
What else could be done simply?