В настоящее время JVM являются однопоточными, но вы не должны полагаться на это, продолжая иметь место: спецификация Java Servlet позволяет контейнерам сервлетов быть многопоточными.
Что касается вашего примера, нет, второму пользователю не нужно будет ждать: App Engine раскручивает несколько независимых виртуальных машин для обслуживания вашего приложения, поэтому второй запрос отправляется на другую виртуальную машину.