There are different types of virtualization and Virtuozzo uses a “shared kernel” architecture rather than doing a full hardware abstraction which is why the kernel can’t be upgraded 
Oh, didn’t know that. That’s too bad, in that case dedicated is the only way. Though I wonder what the benefit of a shared kernel is.
Basically lower overhead to the virtualization (and probably some dynamic memory pooling/sharing). It lets the hosting providers stack more VM’s on a single box.
EC2 and a lot of the cloud providers provide bare-metal virtualization where you can run your own full kernel stack (a micro instance on EC2 might actually be a good cost-effective option).