DaBags, разумеется, это надо делать на этапе регистрации. Даже странно, что возникли сомнения в этом.
Насчёт 5к в действующем проекте - вообще не проблема. Я и на бОльших данных (миллионы) менял структуру таблиц. Пишется простой скрипт (лучше на SQL), база приостанавливается в 4 часа ночи, когда юзеров минимум и таблица обновляется. Время - секунды, а то и быстрее