You can simply go for a cpanel server which now comes with tomcat 7 and jdk 1.7
How much memory you need for the vps depends upon the application you need to run and your developer can give you some idea on the same.
I have seen cpanel vps's running fine with 2 GB RAM when tomcat's Xmx is set to 512 MB or below
1. Not many hosting companies advertise this. Tomcat is software and most are advertising hardware. You need to contact hosting companies who matches your budget for hardware and management. After ask for tomcat and other software you might need.
2. No one will send you an offer here since you posted this request in the wrong section of this forum.
PidginHost.com - Managed dedicated servers, cloud servers and software development.