Пользователь решает задачу на javascript и отсылает код решения на сервер. На сервере программа запускается на тестовом наборе данных и пользователю возвращается заключение о правильности решения.

Как запустить javascript на сервере? (сам сайт написан на php)

Javascript можно исполнять разными способами, начиная от nodeJs до Rhino.

Это все отдельные приложения, которые нужно иметь и запускать на сервере. 

В то же время, существуют уже установленные на каждом броузере JavaScript машины, которые вполне могли бы сами порешать тестовые задачки.
Какого рода задачи будут вводится юзерами и насколько важно выполнять их на сервере?

Задачи простые, учебные - работа с числами и строками. Объекты браузера не нужны. Сейчас студенты обычно запускают программы через Windows Script Host.

Важно, чтоб они не могли узнать, на каких наборах данных тестируется задача, т.к. набор тестов постоянен. И чтоб они не могли обмануть систему, что легко с клиентским javascript, т.к. на основе информации о сданных задачах выставляется оценка.

vorkulsky, Могу порекомендовать nodeJs в качестве инструмента. На сервере (школьном, учебном?) поднимается сервер на nodeJs, который принимает текст задачи на Javascript, формирует окружение скрипта и маскирует системные переменные ядра nodeJs, после чего скрипт запускается, переменные ядра демаскируются.  Пример простого web-сервера на nodeJs есть на его родном сайте в комплекте примеров. 
К сожалению, нужно контролировать расход памяти для такого сервера, так как гарантированно изолировать выполняемый код от ядра на JavaScript довольно сложно...

В качестве менее уязвимой альтернативы можно предложить Rhino. Это Java реализация Javascript. То есть для исполнения каждого теста будет запущен Java интерпретатор Javascript. По завершении теста он прекращает работу и проблемы  грязной памяти не существует. Работает все это, imho, достаточно шустро, хотя для серьезной нагрузки его рекомендовать не стоит. Нагрузка, которую генерируют пара студенческих классов, imho, не достаточно серьёзна...