Да, первая часть псевдонима склоняется, например: судьба Маты Хари.

Обе части псевдонима Аль Бано не склоняются, как и компоненты имени Аль-Капоне.

Кавычки не нужны. Прозвища и псевдонимы пишутся без кавычек (в том числе и сетевые псевдонимы).

Проблемы выбора прописных и строчных букв в личных именах, в том числе в прозвищах, наиболее подробно описаны в статье Е. В. Арутюновой, Е. В. Бешенковой, О. Е. Ивановой  «Прописные и строчные буквы в собственных именах людей, прозвищах, псевдонимах, кличках: из академических правил русской орфографии».

В этом словаре фамилии и псевдонимы набраны прописными буквами – для быстрого поиска нужного имени лица. Правильно: Кукрыниксы.

Написание с двумя прописными буквами Червонная Королева появилось под влиянием английского источника (Queen of Hearts). О проблемах написания приведенных Вами типов названий подробно рассказано в статье «Прописные и строчные буквы в собственных именах людей, прозвищах, псевдонимах, кличках: из академических правил русской орфографии» Е. В. Арутюновой, Е. В. Бешенковой, О. Е. Ивановой.

Сочетание можно осмыслять по-разному, то есть по-разному определять границы имени собственного, и в зависимости от осмысления выбирать графическую форму. Запятая возможна, если считать красный нос приложением, также возможно тире. Дефис объяснить труднее. Можем осторожно предположить, что с помощью дефиса хотели показать слитность, цельность сочетания, которое присоединяется к первой части имени как единый компонент. О собственных именах с приложением можно прочитать в научной статье «Прописные и строчные буквы в собственных именах, прозвищах, псевдонимах, кличках: Проект академических правил». 

Ответ на Ваш вопрос содержится в статье Е. В. Арутюновой, Е. В. Бешенковой, О. Е. Ивановой «Прописные и строчные буквы в собственных именах людей, прозвищах, псевдонимах, кличках: из академических правил русской орфографии». 

«При упоминании того или иного персонажа литературного произведения в другом произведении статус имени может меняться, — пишут исследователи. — Например, в сказке А. С. Пушкина «Сказка о мертвой царевне и семи богатырях» сочетание мертвая царевна не является именем собственным, но если в другом произведении говорится именно об этой мертвой царевне, то автор вправе отнестись к нему как к имени собственному, т. е. правомерно написание Мертвая царевна».

Таким образом, вопрос о границах имени собственного решается автором текста. Орфографические правила позволяют современному автору превратить пушкинского ученого кота в своем произведении в Ученого кота.

Это выражение по-разному фиксировалось в словарях и справочниках. Сейчас корректным является написание, соответствующее рекомендациям новейшего академического орфографического словаря – «Русского орфографического словаря» под ред. В. В. Лопатина и О. Е. Ивановой (4-е изд. М., 2012).