A ver, con PHP, MySQL y Ajax es posible, pero creo que lo mejor es usar una herramienta prefabricada (claro, si el proyecto lo permite), el otro día le dí esta link a otro usuario:
http://www.123flashchat.com/video-chat.html
Sobre el servido, pues mínimo un VPS y después tendrás que contratar un servidor dedicado si llega a crecer tanto.
Saludos
