В названиях памятников, мемориальных сооружений, комплексов с прописной буквы пишутся первое слово и последующие слова, выражающие высокие понятия. Поэтому правильно: Аллея Трудовой Славы.
Оба варианта верны. Об угле и углях см. в электронных словарях на нашем портале:
Орфографический словарь
уголь 2, угля, мн. угли, углей и уголья, угольев (кусок обгоревшего дерева)
Словарь трудностей
Да, эта фамилия обязательно должна склоняться: Кулеша Андрея, Кулешу Андрею и т. д.
Если слово "уголь" используется в значении "вещество", а не "куски обгоревшего дерева", то нужно использовать форму ед. ч.: марок угля.
Клеить – глагол 2-го спряжения. Правильно: клеят.
Правильно: Доска почета, Аллея Славы.