См. http://dev.mysql.com/doc/refman/5.1/en/create-index.html
Существует хранимая процедура, которая делает это (запомните, не мой код, только первое нажатие на Google с mysql add index if not exists
в качестве строки поиска).
DELIMITER $$
DROP PROCEDURE IF EXISTS `create_index_if_not_exists`$$
CREATE DEFINER=`user`@`%` PROCEDURE `create_index_if_not_exists`(table_name_vc varchar(50), index_name_vc varchar(50), field_list_vc varchar(200))
SQL SECURITY INVOKER
BEGIN
set @Index_cnt = (
select count(1) cnt
FROM INFORMATION_SCHEMA.STATISTICS
WHERE table_name = table_name_vc
and index_name = index_name_vc
);
IF ifnull(@Index_cnt,0) = 0 THEN set @index_sql = concat('Alter table ',table_name_vc,' ADD INDEX ',index_name_vc,'(',field_list_vc,');');
PREPARE stmt FROM @index_sql;
EXECUTE stmt;
DEALLOCATE PREPARE stmt;
END IF;
END$$
DELIMITER ;
На той же странице прямо под ним есть альтернативная версия.