Чат на PHP

От аякса не отказывайся - это не так уж и сложно.
Для ещё большего упрощения\облегчения жизни можно воспользоваться библиотекой jQuery. О jQuery можно почитать для начала вот это:
http://habrahabr.ru/blogs/webdev/31239/
http://www.rsdn.ru/article/inet/jQuery.xml
http://blog.termit.name/jquery/

Для того, что бы подгружать только новые сообщения, нужно каждому сообщению присвоить уникальный id (что, в общем-то, и будет автоматически делаться, если исользовать SQL базу и предусмотреть поле id с автоинкрементом) . При заборе же новых данных с сервера нужно будет указывать - какое сообщение уже было получено последним.

Где хранить сообщения - это уже твой выбор, но для начала - в базе будет это делать легче. Тем более что использование БД и так планируется.

Лично я решил данную проблему кардинально - ввел константу (например STR=50) и записывал в файл только последние STR-строк, остальное бесследно пропадало. Соответственно и пересылалось только STR-строк. После, ориентируясь на пожелания ЧАТланцев, довел значение STR до приемлимого значения. И всё.
Писал на PERL, могу скинуть исходники - думаю разберешься.
С БД не работал, но общался в парочку ЧАТах, где периодически довольно часто появлялось сообщение типа "Извините, произошла перегрузка БД, идет очистка базы данных".
У меня таких проблем никогда не было. Да и к чему хранить разговор даже 5-минутной давности? Для чего?
Если уж применять MySQL, то только для приватных сообщений, да и то сложновато-мутновато. Я хранил "приватки" в личных файлах пользователей и подкидывал их адресно к общему экрану.

Вот вам идея (подсмотрена мною в каком-то чате много-много лет назад) : сами сообщения выводятся во фрейме, причём сервер постоянно выдает поток информации: когда новых сообщений нету, то приходит просто пробел (что не изменяет количества сообщений) или новое сообщение (при добавлении кем-то из участников) . Поток данных попросту идёт всё время.. . и прерывается только при выходе участника чата из чата.. .
В другом фрейме стоит форма отправки сообщения, состоящая из поля ввода и кнопки Send - обработчик формы принимает сообщение и передает текст сообщения процедуре, которая выдает порцию информации в фрейм с сообщениями.
Таким образом достигается неперегружаемость фрейма с сообщениями и непрерывностью прихода новых сообщений.

ДАДАДА.... храни сообщения чата в базе! Красава! :)

Если не хочешь перегружать страницу, то тебе в любом случае придется прибегать к технологии AJAX. Там кстати ничего сложного нет. Надо просто разобраться - пара-тройка часов и впрягешься.
Хранить сообщения думаю лучше в БД.

На вот почитай про АЯКС:
http://www.ibm.com/developerworks/ru/library/wa-ajaxintro1/

без аякса, почти без жаваскрипта и перезагрузки страницы можно вот так:
сделать 2 фрейма. В одном фрейме будет форма с отправкой сообщения, в общем, ничего мудреного.
Во втором фрейме будут потоком идти все сообщения так, что страница по мнению браузера будет как бы постоянно грузиться. Сообщения должны приходить регулярно, иначе браузер закроет соединение по таймауту, так что примерно раз в минуту, если нет новых сообщений, надо присылать хоть что-то, пустой комментарий HTML например.
Дальше, поскольку соединение открыто, твой пхп скрипт, относящийся к этому фрейму будет работать по экземпляру на пользователя. Чтобы отправлять новые сообщзения без буферизации, используй flush. И еще, в самом начале, для того чтоб браузер хоть что то отобразил на экране, размер первой загруженной части должен быть около 1 кб. То есть, что то такое:
// проверить авторизацию
// отправить 1кб мусора - заголовки html, вспомогательный жаваскрипт
while(1) {
// проверить БД, есть ли новые сообщения для этого пользователя.
echo( новые сообщения );
// проверить таймаут и если надо то отправить пустышку
flush()
}
Еще, конечно, надо вставить в этот фрейм жаваскрипт прокрутки окна вниз при приходе каждого нового сообщения, и еще можно, на случай разрыва соединения, добавить обновление страницы на событие onload, ведь оно произойдет только если соединение будет разорвано

Без перезагрузки страницы только JavaScript(ajax)/Flash/Silverlight/Java Если использовать только серверный язык, такой как php, то только с перезагрузкой.