If you were only interested in 'z', you could create a function-based index.
CREATE INDEX users_z_idx ON users (INSTR(last_name,'z'))
Then your query would use WHERE INSTR(last_name,'z') > 0
.
With this approach you would have to create a separate index for each character you might want to search for. I suppose if this is something you do often, it might be worth creating one index for each letter.
Also, keep in mind that if your data has the names capitalized in the standard way (e.g., "Zaxxon"), then both your example and mine would not match names that begin with a Z. You can correct for this by including LOWER in the search expression: INSTR(LOWER(last_name),'z')
.