I can see two possibilities that you might consider reasonable. One would be to build a stub executable with a different compiler (e.g., MinGW -- whatever, just so it doesn't need cygwin) to unpack the main executable and cygwin.dll into a temporary directory, and then spawn that executable. To distribute only a single executable, you'd want to add the main executable and cygwin.dll to the "stub" as binary resources. It's a bit ugly, but pretty straightforward.
The alternative would be to grab the source to cygwin, and build it as a static library. At least in theory, this should be cleaner -- but it's also undoubtedly more work. Getting it to build as purely static code instead of a DLL will almost certainly take some work, though it's hard to even guess how much. Just browsing a bit, it's seems pretty unlikely that it's going to be a quick job of a couple hours, or anything like that (unless there's something there that I missed that already supports building it statically, of course).