Trouble installing percona 5.6 on Google compute engine debian
I was having the exact same problem on an AWS t1.micro that has about .6GB of memory. It would go through the entire setup process then fail on initializing mysqld. As it turns out, that instance did not have enough memory to get percona server 5.6 going. I brought up a faster instance running 3.75GB of memory and it started without issue.

If I were to speculate, I would guess you are on the f1-micro instance which is why you are getting the "Cannot allocate memory" errors. Try the g1-small instance and see if that is enough to get mysql running.

Update:
I was/am using Percona's default configuration and I was able to successfully install on a Digital Ocean droplet with 1GB of memory. So, it seems as though the magic number of needed memory is between .6GB and 1GB.