добавляем колонку к баннерам в БД:
lastshow: [timestamp]
X: 5(часто),15(обычно),30(редко)
now()-lastshow>X*60 показываем случайной выборкой из списка и записываем в lastshow
Выбор баннера для показа "частых":
SELECT * from banners where NOW()-lastshow>5*60 RAND() LIMIT 1
Далее запрашиваем для "обычных", меняя 5 на 10 и т.д.
Как только наберется в списке нужное кол-во - прекращаем и выводим.