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