This is exactly what you should do. Your users will understand -- that's why so many have supported you on the googlegroup. Charge $3/mo and you won't hear any complaints (and if you do, you can point to your googlegroup).
This is by far your easiest and clearest path to monetization, at least that I can see. And it seems you're long overdue for monetization.
Can you adjust the sync rate depending on the time of day where your users live? There are probably certain times of the day when people update their tasks less frequently.
For premium users sync every minute.
Use Indian payment gateways if possible, though Paypal works fine too.