Hi David,
In order to establish trust without the use of PKI you need some method of secure, Out of Band communication, e.g. go and manually install the self-signed certificate in a client's keystore. If you expect to have multiple servers and multiple certificates, you should generate your own CA and add the CA's certificate to the list of trusted root CAs. Note that if this is for an organization (e.g. a server that sits on an intranet) you should also consider setting up an OCSP server when configuring the CA, so that you can safely perform certificate revocation in the future.
Security tip: If you go the custom CA route, remember that you don't need to put the CA private key on the server!