Stack Exchange network consists of 183 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.
It's worth noting that the question contains a counterexample to Leinster's claim: virtual double categories do not subsume skew-monoidal categories, yet categories may be enriched in skew-monoidal categories.
@DavidWhite: I've added some links for context, and provided a little background on my motivation for asking this question. Tim Campion's answer explains what would be needed for a resolution to this question: i.e. a syntactic interpretation of the structure that characterises algebraically exact categories, but I don't believe anyone has studied all of these properties syntactically so far.
@DavidWhite: thanks for the suggestion. I've added a couple of links. My motivation for this question was primarily abstract: it seems a natural concept to consider (and indeed, Kan did), and I was wondering if it had been studied anywhere. Kan does not give any convincing examples.
@DavidWhite: I am pretty confident the approach I suggest would work to give a non-universal construction of such an embedding, but I would still be interested in a universal construction, which is why I have left the question open. I know of a partial result along these lines, which I will mention as an answer, though.