If its as simple as downloading an app and letting it stake, advertisements should be plastered on every android related website you can find, possibly a donation fund for promotion would be good if not one already.
GL
This is a great idea. Do you know of some good Android user site that we should list it up on? As for coins if you have none and want to test it you can always come to the irc https://kiwiirc.com/client/irc.freenode.net?channel=#librexcoin channel where some small samples are "rained on you" once in a while. when you get some you can test the app. So that pretty much is a free sample.