Hello Aswath,
You are right, you cannot install software in GAE, as local system is not accessible, or writes are not persistent. Which environment do you refer to: Standard or Flexible?
In fact, you don't need to organize your own cron system, you can simply use
Cloud Scheduler, a solution made for GAE, which does not require such set up effort as you seem to plan for.
By contrast, you can do whatever you please and install your debs on a VM instance in
Compute Engine.