Is it possible to have a single trial per device?
Is it possible to provide a service in which one free trial is given to each device without the possibility of an individual being able to get multiple free trials on a single device. If its impossible, do you know of a way of making it difficult to obtain multiple free trials.
You can generate the license key based on the device's unique ID, the request date, and your own private key to create a license that is only valid up to certain date.
You application will verify that the license key is valid by decoding the license key with your public key, and comparing its expiration date and device ID. People can't forge a bogus request, since the license key is only valid for the prescribed date and a given device ID.
(hint: read about public-key cryptography)
However, it's not totally foolproof. A really determined attacker can root his device, and install a custom firmware which allows him to control identifier returned by "getDeviceId()". This isn't something that most people would be willing to do, most people would rather find an alternative free app or just buy the app rather than going through that route. Against crackers with that sort of determination and skills, there is not much you can do about.
Alternative avenue of attack would be to replace the public key you ship with the application with the attacker's private/public key combination, and he can potentially write a key generator that can generate license key for the forged application. You can make this attack difficult by self-verification of your own executable.
However, no security scheme is foolproof, java/android application can be reverse engineered and a determined hacker can forge your application and disable its license checks. The only foolproof way to prevent unauthorized usage of an application is to not distribute the application at all.