Can I virtualize Lion on Apple hardware running Linux without violating the EULA?
Unfortunately you cannot virtualize OS X Lion under any other OS except OS X Lion. It's not enough that it's running on Apple hardware.
The OS X Lion EULA says:
Section 2, Sub-Section B:
(iii) to install, use and run up to two (2) additional copies or instances of the Apple Software within virtual operating system environments on each Mac Computer you own or control that is already running the Apple Software.
Bolding is mine and it highlights the relevant passage that prevents you from virtualizing OS X on Apple hardware where the host OS is not also OS X.