Without regular expression, but you are turning the logic around to make use of the % wildcard in LIKE. I think this is pretty close to the logic that you had in mind.
SELECT DISTINCT(CITY)
FROM STATION
WHERE 'aeiou' LIKE CONCAT( "%",LEFT(CITY, 1),"%")