I'd use the Web SQL Database stuff that W3C was working on, except that they stopped doing that in 2010, which guarantees the corpse is dead and rotting; unfortunately, the only emulation libraries I've been able to find implement various key-value stores on top of WebSQL, which is the precise inverse of what I'd need.
I suppose it'd be theoretically feasible, albeit hideously ugly, to create and populate a fresh database and account per user on a MySQL engine; with careful grants and a bit of scripting to kill slow queries before they can multiply and throttle the server, that might be workable on the small to medium scale, although I don't doubt a "Show HN" post would kill it in short order.
Thinking about it, I suspect I've more or less recapitulated why there is currently no "You Can't SQL Under Pressure"; it's a more subtle problem than it seems at first blush. If you come up with any clever ideas on the subject, I'd love to hear about them!