To recap: you are setting up webservers on desktop apps; each desktop will have its own webserver, but you want to use SSL to secure the connection to that webserver.
I guess there are several problems here with certificates, one being that the hostname used to access the desktop has to match the certificate. In this case you have little choice but to generate certificates on the client. You'll need to allow the user some way to specify the host name in case the name used by outsiders can't be detected from the host itself.
I'd also suggest allowing for an admin to install a trusted cert, for those who don't want to rely on self-signed certs. This way you can also offload the cost of trusted cert maintenance to the admins who really want it.
Finally, in my experience browsers either allow or refuse the self-signed cert and there is no way for the server to know if the cert is denied, or temporarily accepted, or permanently accepted. I assume there must be a mechanism somewhere to handle SSL failures but typical web programming doesn't operate at that layer. In any case, the only thing a webserver can do if SSL fails is to fallback to non-SSL, and you've indicated in a comment that you can't have anything non-SSL. I think you should try to have that restriction lifted; a non-SSL start page would be extremely helpful in this situation: it can test (using frames or images or JSON or AJAX) the https connection, and it can link to documentation about how to set up the certificate, or where to download an installer for the cert.
If the browser won't connect because of a self-signed cert, and you're not allowed to use plain HTTP at all, by what other means could you communicate with the user? There are no other channels and you can't establish one because you don't have any communication.
You mentioned in a comment writing a win32 app for installing the cert. You could install a cert at the time you install the application itself, but that doesn't help any remote browsers, and a local browser doesn't need SSL to access localhost.