I would like to have two apps. One to do the real job and another one to carry the payment on a monthly basis (licensing app).
Users must download the licensing app each month from Market. But, should they have to uninstall the last month's app before that?
Can an app auto destroy itself (uninstall itself)?
Check out the new in-app billing functionality, you may be able to use it to bill time/subscription renewals.
You have three options.
Option 1 - Your solution, where the user must install a new payed app every month (code on how to uninstall an app follows).
Option 2 - Make a server/authentication solution, where the app pings a server to ensure the user has payed for that month.
Option 3 - Make your own version on Apple's in-app purchases, where the user can say, pay via Paypal every month to keep the app running.
Code to uninstall apps:
Intent intent = new Intent(Intent.ACTION_DELETE);
String packageName = "com.example.app.package";
Uri uri = Uri.fromParts("package", packageName, null);
intent.setData(uri);
startActivity(intent);
Your app would need the android.permission.DELETE_PACKAGES permission to run the above code.
You have to create a complete new app each month, because a once payed app stays payed even if you uninstall your device and/or reset it. The information which app you have bought is tied to the account you use.
To get a monthly fee, you need to work with another system then the android market... I cant think about a user who want to download a new "payed" app each month...