Если нужно универсально, и чтобы заменяло только первые три символа, то можно выкрутиться вот так:
UPDATE table
SET field = CONCAT('456', SUBSTRING(field, 4))
WHERE field LIKE '123%';
Но опять же, это только если заменять нужно точно известную подстроку.
Есил заменять нужно в середине, тоже можно выкрутиться с помощью SUBSTRING_INDEX() или LOCATE().
Между прочим, решение без регулярок будет быстрее, чем с ними, и, к тому же, универсальнее. А следовательнее, его лучше предпочесть, если это возможно.