So run multiple instances of the app, and put some kind of load balancer / proxy in front of the instances.

Unfortunately, this will require externalization of state data, but if you can't be down for 5 minutes, that's what you need to do.

You probably only need one large server running the instances, rather than a cluster. Java apps don't seem to do well -- longer GC pauses -- when they have over 2 GB of memory, anyway, so run multiple instances of "small" apps on a server with say 12 cores. A single server with a large pool of RAM shared between a large number of cores can do pretty amazing things with a collection of "small" programs on it (DB, web service apps, message queue server, web servers)

Of course, I'm assuming said server isn't Windows...