I have a server with 500 MB RAM (VMware ESXi doesn't fit...). What are possible solutions for running Windows Server 2003 and Gentoo/Debian on the same system, at the same time? Also, it would be best if I wouldn't need to run third OS to emulate those two...

You could try OpenVZ on Linux distro's like CentOS or Debian.

It's a bad idea to not run a third OS or a dedicated/seperated hypervisor to domain 0, since your already scrapping the barrel on memory, Windows 2K3 (standard/web) is a minimum 128MB of RAM, recommended is 256MB so that's half of your RAM, and Debian would probably need a minimum of about 64MB? it's hard to tell since they don't directly specify, generally it's probably going to be recommended to have 128MB minimum... and this is before your hosting anything and without virtualition requirements. If one hosts the other, and the primary domain crashes, it takes down the entire system. So it's not a good idea what you are after, you really want a machine with a minimum of 756MB of RAM but preferibly 1GB.

Also on CentOS it's a minimum 256MB of RAM (it WILL refuse to install if it does not have 256MB of RAM free during installation).

He could be right, didnt play with so low memory in ages, so listen to the guy.

Good luck anyway!