Have you thought about using an installer? For example, we've used InstallAnywhere by ZeroG, and it's excellent. You can definitely bundle your own JRE in the installer.
It offers fully customizable installation, but very easy to set up and use. Builds installers for most platforms, and gives the user a clickable icon/shortcut to start the app. Takes care of all the classpath issues behind the scenes, so your user never needs to know. Take a look:
http://www.zerog.com
The InstallAnywhereNOW! version is free, and the other versions have a trial download