Adding index columns for columns that only have three or so possible values won't improve performance.
If you can't fix the tables, it may be necessary to build an intermediary reporting table that can be queried more efficiently.
Just for laughs, is this much faster?
select
start.datetime as start_datetime,
min(end.datetime) as end_datetime,
(unix_timestamp(min(end.datetime))-unix_timestamp(start.datetime)) as duration
from hosts h
left join servicechecks s on h.id=s.host
left join state_history start on s.id=start.servicecheck
join state_history end on start.servicecheck=end.servicecheck
and end.datetime>start.datetime
and end.status="ok"
and end.status_type="HARD"
where start.status="CRITICAL"
and start.status_type="HARD"
and start.datetime between "2013-12-01 00:00:00" and "2013-12-31 23:59:59"
group by start.datetime;