I am presently running multiple VMs at work. With 256Mb I can comfortably run Apache on CentOS with PHP. So, you should be able to handle it with 384Mb. Unfortunately, if I am not able to run java/Tomcat on it until I increase the memory.
Depends on the kind of VPS technology used. If the provider uses OpenVZ/VServer, you will be able to save several tens of MB of memory from running the Linux kernel. However, if it uses something like Xen, you will need to spend some memory on the Linux kernel.
If you do not need to use Apache, avoid using it. There are plenty of other light-weight web servers around. You have already mentioned nginx. You can also try lighttpd and I think that many RoR sites use it.