Build Python with Mingw and gcc
First off, you do not need to build Python with MinGW-w64 to link to it and embed a interpreter. Just extract the msi installer, and use the prebuilt DLL. Note you'll have to be careful not to mix msvcr[t|90].dll objects, but I've never seen that be a real issue personally.
MinGW-w64 gcc/ld should be able to link to DLL's directly, otherwise you'll have to use gendef to create a .def file and dlltool to create an import library.
Secondly, there's a patchset to build Python with MinGW, but I'm not sure about its 64-bit compatibility.
You may try this repository:
hg clone https://bitbucket.org/puqing/python-mingw
It is a copy of the official repository but contains some modification to make it compile with mingw. Enter PC/MinGW directory:
cd PC/MinGW && make
Not sure if it compiles in win64, but with win32 and msys it should work.