char * a = "hello!";
Для указателя a — разумеется, на стеке.
Строка, на которую он смотрит, "hello",— строковый литерал. Для него память изначально, при пуске программы выделена в сегменте данных. Освобождать не надо. На многих платформах — хоть на это рассчитывать не надо — этот сегмент защищается от записи и при попытке туда записать AV.