Сочетание всему голова в современном русском языке устойчивое (ср. словарную статью существительного голова в Большом толковом словаре на нашем портале, где сочетание приводится среди фразеологизмов, за знаком ромба), а поэтому к нему применимо правило постановки тире перед именным сказуемом, выраженном фразеологическим оборотом.

Знаки препинания ставятся по общему правилу: если однородных членов предложения более двух, а союз повторяется перед каждым из них, кроме первого, то запятая ставится между всеми однородными членами. Верно: Он не мог сообразить, когда, и как, и за каким же чертом пришел в это место.

В этом сложноподчиненном предложении перед придаточной частью стоит частица и со значением 'тоже, также'. Такие предложения упомянуты в параграфе 115 полного академического справочника «Правила русской орфографии и пунктуации» под ред. В. В. Лопатина (М., 2006 и след.) среди случаев, в которых запятая не ставится.

В первых двух случаях кавычки и прописная буква не нужны. Слова король и королева используются в устоявшемся значении 'о том (той), кто является первым, самым лучшим среди других, кто достиг совершенства в чём-л.'. Третье сочетание условно, окказионально (единично), поэтому корректно в таком написании: звание «железной леди». 

В поэтическом тексте, как и художественной речи в целом, возможно многое. Оценить уместность данного словоупотребления в столь небольшом контексте трудно. Ср. употребление сочетания в переменах, например, у А. А. Фета:

Нет! В переменах жизни тленной
Среди явлений пестрых — ты
Всё лучезарный, неизменный
Хранитель вечной чистоты.

Если однородных членов предложения больше двух и союз и повторяется хотя бы дважды, запятая ставится между всеми однородными членами (в том числе и перед первым и): Я взобрался на гору сена, и непослушными руками схватил вилы, и от кого-то снизу принял первый вилок, и хотел его поднять, но...

Номинации крупные города и города-миллионники стали использоваться в научной и профессиональной речи еще в 80-е годы ХХ века. Интенсивная урбанизация и ее изучение сопровождались появлением вербальных новшеств, среди которых оказались слова миллионер и миллионник. В настоящее время именно обозначения город-миллионник или миллионник употребляются в текстах экономической и социальной тематики.

В этом случае нет оснований игнорировать указанный Вами пункт правил, тем более что в качестве примера в нем приводится, среди прочих, название «двойной должности» директор – художественный руководитель (в сочетании обратиться к директору – художественному руководителю). Структура названия должности в Вашем случае аналогична структуре названия из этого примера.