Since a computer virus isn't much different being code at the core, you could very likely build a self-replicating contract that can auto-execute other functions. Ethereum contracts are essentially autonomous agents that can perform many functions.
Wouldn't that be very expensive in terms of ether fees? As I understand Ethereum favours short programs because it charges fees per executed line of code.
https://github.com/ethereum/wiki/wiki/%5BEnglish%5D-White-Paper#wiki-feesYes, this was my main criticism for Ethereum's current solution. You can store a movie in their blockchain, but its going to cost you $1,000. When I implement this in the Ethereum chain I'm going to use my metadata solution. Essentially you only store where the stuff is not the actual stuff.