Great news to hear that such a service is in the making!
I'm thinking that PoW could be done on the server side with the following way:
The service owner owns or rents a pool of powerful CPU (or GPU) nodes. These nodes will have full-IOTA db and will be in sync 24/7. Each web session will be a connection to one of these full nodes, using random selection. When the user submits an action that needs PoW, the PoW will be done in one of these servers and the answer is shown to the user.
The user will not know (does not care) which server performs the PoW, he just sees the results.
Another way would be that all of these servers also host the web service, perform the PoW locally in them and then respond back to the user (so that the randomly selection layer is put one level up = during the web session establishment, hosting web content and resources). With the first way, the web site is hosted on a different server (and not on a fully IOTA connected node, having the random selection performed later, when a PoW action is needed).