самый простой способ — сделать фри-версию с рекламой. плюс — in-app purchase — дабы пользователь мог внутри приложения купить ad-free.
таким образом, у вас не будет отдельного приложения без рекламы — которое надо защищать и не давать копировать.
пользователь в целом не имеет возможности подделать уведомления о покупке чего бы то ни было через google in-app purchase.

плюс, конечно же, надо использовать обфускатор кода. хотя бы встроенный proguard.
плюс — не хранить в открытом виде важные для проверки подлинности строки — а как-нить хитрым образом их получать.

плюс — есть возможность получить ID устройства. который, теоретически, никогда не меняется. если надо — могу написать метод, которым его можно получить. из-за бага — встроенное получение кода может глючить в андроиде 2.2 и ниже. но и это решается. ну и нарисовать свой сервер, который хранит — кто купил, а кто — нет.

но самый лучший способ — действительно — ввести халявщиков в бизнес-модель приложения.
попытаться понять — как Вы их сможете использовать.
варианты.
1. реклама.
2. в принципе, халявщий может через какое-то время проникнуться и заплатить.
3. халявщики способствуют росту популярности приложения — и как следствие, росту продаж.
4. есть есть всяческие in-app purchase — и разводка пользователя на эти микротранзакции — то можно и бесплатно скачивать. главное — чтобы потом платили.

но это всё не отменяет желательности обфусцировать код.