Amazon is definitely something into which you should look. They have a free option that offers pretty good performance. They also have paid options with different scaling schemes. You can buy capacity in advance (the cheapest) or pay for it on demand (more expensive but you only pay for what you use as you use it) as well as some other schemes. They also have pretty good DNS services and offer even the free accounts quite a few IP addresses.
As for operating systems, they offer a bunch of Linux and Windows options. You can install Java 8 on either OS and run your B4J servers there. With the Windows option, you can use Remote Desktop Connection to connect to your AWS instance whereas with the Linux options, you're going to be using SSH.
Security is pretty solid on AWS provided you make use of what Amazon provides. There have been some very interesting data "leaks" from AWS instances but that was because the people running the instances were doing so without any of copious security Amazon provides in place.