Use CreateDIBSection to create a 8bpp bitmap, and BitBlt onto that.
Filling in the BITMAPINFO structure is going to be the interesting. You can't use a normal BITMAPINFO struct as it only allocates space for a single palette entry and, with a 8bpp image - you will need the full 256 entries.
If you want to cheat a bit, one can use a anonymous union to declare a BITMAPINFO with enough space for its palette.
union
{
BITMAPINFO bmi;
struct {
BITMAPINFOHEADER bmih;
RGBQUAD extra[256];
} dummy;
};
bmi.bmiHeader.biSize = sizeof (bmi.bmiHeader);
bmi.biBitCount = 8;
// and so on.
As to the values to initialize in the color table... I can't think of an easy way to get a default 8bpp palette from GDI when its not in 8bpp mode. I have a suspicion that CreateHalftonePalette isn't going to do anything on a non palette device.