There's a lot of ways you can do this.
You didn't mention what kind of app it is and what operating system it runs on. This could yield some specific ways of marketing.

If your app is sold on itunes, consider contacting the yahoo writer who releases "free today apps" on their columns.

Get an invite to producthunt.com

Leverage personas through instagram with pictures

build an audience through facebook groups for possible users of your app...