Корректно: инкрустировать самоцветами.

По сути бренд - это торговая марка. Можно сказать: товары производятся под таким-то брендом. Какой смысл Вы хотите вложить в требуемое сочетание?

Думаем, что возможны оба варианта.

Отсутствие склонения части Ван в именовании Винсента Ван Гога объясняется тем, что Ван здесь — служебное слово. Согласно правилам орфографии служебные слова (артикли, предлоги и др.) ван, да, дас, де, делла, дель, дер, ди, дос, дю, ла, ле, фон и т. п., входящие в состав западноевропейских и южноамериканских фамилий, пишутся со строчной буквы, напр.: Людвиг ван Бетховен, Леонардо да Винчи, Оноре де Бальзак, Лопе де Вега, Альфред де Мюссе, Хуана Инес де ла Крус, Лукка делла Роббиа, Андреа дель Сарто, Роже Мартен дю Тар, Женни фон Вестфален, Макс фон дер Гоюн, Жанна д’Арк; Ортега-и-Гассет, Риего-и-Нуньес. Однако в некоторых личных именах служебные слова традиционно пишутся с прописной буквы (как правило, если прописная пишется в языке-источнике), напр.: Ван Гог, Д’Аламбер, Шарль Де Костер, Эдуардо Де Филиппо, Ди Витторио, Этьен Ла Боэси, Анри Луи Ле Шателье, Ле Корбюзье, Эль Греко, Дос Пассос.

Запятая ставится.

А. А. Зализняк в примечании об именах собственных в «Грамматическом словаре русского языка» писал, что некоторые составные имена вошли в русский культурный фонд как целостные единицы, например: Тарас Бульба, Санчо Панса, Ходжа Насреддин, Леонардо да Винчи, Жюль Верн, Ян Гус. Среди них есть такие сочетания, в которых первый компонент в реальном грамотном узусе не склоняется (читать Жюль Верна, Марк Твена), склонение имен в подобных сочетаниях — пуристическая норма, соблюдаемая в изданиях. А. А. Зализняк к таким склоняемым формам дает помету офиц. В некоторых именных сочетаниях первый компонент никогда не склоняется, к ним относятся, например, имена персонажей Дон Кихот, Дон Карлос. Цельность, нечленимость этих сочетаний проявляется и в орфографии. Ср. написание и форму имени, относящегося к реальному историческому лицу и персонажу драмы Шиллера: За XIX век реликвия сменила нескольких хозяев и в 1895 году попала в руки дона Карлоса, графа Мадридского и легитимного претендента на французский трон и Роль Дон Карлоса создана, так сказать, по форме его таланта. 

Псевдоним Аль Бано, к сожалению пока не зафиксированный в лингвистических словарях, можно отнести к категории целостных языковых единиц. Мы наблюдали за его употреблением в разных источниках: первый компонент устойчиво не склоняется. Способствует этому его краткость, совпадение по форме с арабским артиклем.

Корректными считаются оба варианта.

Действительно, рекомендации словарей претерпели изменения, языковая норма меняется.

«Словарь современного русского языка в 17 томах» в 1991 году отмечал только вариант броня (указывая на бронь как просторечное, нелитературное слово). В новом же издании словаря («Большой академический словарь русского языка», том 2, 2005 г.) есть броня (общеупотребительное) и разговорное бронь 'официальное закрепление за кем, чем-либо льготных прав на пользование чем-либо, получение чего-либо'.

Вот как это слово раньше фиксировали словари. 

• В «Толковом словаре русского языка» под ред. Д. Н. Ушакова – два ударения при одном заголовочном слове: броня. Значения слова объединены в одной словарной статье: 'воинский доспех'; 'защитная облицовка'; 'запрет, налагаемый властью на какие-либо предметы общего пользования с целью обеспечить их для кого-либо, для каких-нибудь государственных нужд' (новое, официальное слово); 'предметы, на которые наложен такой запрет' (новое, разговорное слово); 'право пользования такими предметами, документ на это право' (новое, разговорное слово).
•  В «Словаре русского языка» С. И. Ожегова (1952) – броня и просторечное бронь. Такая рекомендация сохранялась в последующих изданиях словаря, а также в большинстве других нормативных источников.
• В «Кратком словаре трудностей русского языка» Н. А. Еськовой: только броня в значении 'закрепление за кем-чем-либо': броня на билеты. Восклицательным знаком сопровождается помета: «!неправильно ед. им. и вин. бронь».
• А вот в «Большом толковом словаре русского языка» под ред. С. А. Кузнецова – только бронь. Другого варианта нет.

С точки зрения литературного языка оба явления — и брань, и просторечие — считаются средствами, выходящими за рамки нормативного употребления.