There are now some companies which provide non-signature based anti-virus detection to potentially detect zero-day malware. Most of them work by spinning up a vm, run or open the file to check, and verify any changes to the system. Check out http://www.fireeye.com/ (funded by the CIA's startup incubator In-Q-Tel) http://www.fidelissecurity.com/ (from General Dynamics) and Northrop Grumman is releasing one soon too.

Not sure if I'd trust these companies more or less than the signature based companies.