By instances you seem to mean CloudSQL server instances, not AppEngine SQL client instances. CloudSQL is MySQL based and the scope of a MySQL lock is indeed limited to a single server instance. Replication copies SQL data but not sessions or locks. Therefore your measured results make sense.
It may not work for you, but you could keep the number of CloudSQL instances down at 1 but increase the number of AppEngine server instances, which will be CloudSQL clients. Hopefully that delivers some of the scalability without sacrificing consistency (pessimistic locking). Your predicament is an inevitable manifestation of the CAP theorem.