I used the python35.dll in the embeddable install, along with the python35.zip included in there. I linked against python.h and python35.lib from a full install, but put the resulting exe in the directory with the embeddable install so it uses that instead of the main one.

Probably I ought to write up a more detailed walkthrough on how to customise the embeddable install, but your feedback here is very valuable. Did you do things differently from what I put above? You're certainly not the only one to do whatever you did.