Uma maneira seria usar uma 'mesa de calendário', ou se você estiver interessado apenas em um dia, uma 'mesa de relógio' serviria. O seguinte ilustra (aproximadamente) como você o usaria.
SELECT clock.time AS available
FROM clock
LEFT JOIN bookings ON clock.time BETWEEN bookings.from AND bookings.to
AND bookings.date = '2013-01-01'
WHERE bookings.id IS NULL
http://www.brianshowalter.com/calendar_tables é um exemplo de como criar um calendário no MySQL
