¿Cómo se adquieren usuarios para una aplicación de Android sin subirla al mercado de Android?

La respuesta corta es que es muy desafiante.
Respuesta larga:
El desafío que enfrenta es de descubrimiento. Como está en el Android Market repleto de más de 300,000 aplicaciones, encontrar una sola aplicación es complicado. Hay un tema completo dedicado a él que puede encontrar en Recomendaciones de aplicaciones y Descubrimiento:
Ciertamente, el marketing, los códigos QR para facilitar el descubrimiento, las redes sociales, etc. ayudarían con el descubrimiento de aplicaciones, pero tiene otro obstáculo que superar una vez que haya intrigado a algunos usuarios lo suficiente como para descubrir su aplicación.
Primero, sus usuarios potenciales tienen que confiar en que su aplicación proporcionará el valor anunciado, no será spam o, lo que es peor, un malware. En segundo lugar, sus usuarios potenciales se convencen de que su aplicación es útil, entonces tendrán que ser lo suficientemente inteligentes o tendrán que ser educados sobre cómo descargar e instalar una aplicación desde una fuente que no sea Android Market.
Hay otras alternativas como la tienda de aplicaciones de Amazon GetJar o Carrier Markets que podría probar, pero todas enfrentan los mismos desafíos que mencioné anteriormente. Además, dependiendo de las políticas del operador, pueden o no permitir algunos de estos mercados secundarios en los dispositivos.