How I can change prefixes in all tables in my MySQL DB?

zerkms solution didn't work for me. I had to specify the information_schema database to be able to query the Tables table.

SELECT 
    CONCAT('RENAME TABLE ', GROUP_CONCAT('`', TABLE_SCHEMA, '`.`', TABLE_NAME, '` TO `', TABLE_SCHEMA, '`.`prefix_', TABLE_NAME, '`')) AS q
FROM 
    `information_schema`.`Tables` WHERE TABLE_SCHEMA='test';

Edit:

Optimized the query to only call RENAME TABLE once. Something I walked into was the fact that the concatenated output got truncated at 341 characters. This can be solved (if allowed by your server) by setting the MySQL variable group_concat_max_len to a higher value:

SET group_concat_max_len = 3072; -- UTF8 assumes each character will take 3 bytes, so 3072/3 = 1024 characters.

PhpMyAdmin allows you to do this now. At the "Database" level select the Structure tab to see all the tables. Click 'check all' (below the table listing). On the 'With selected' dropdown choose: 'Replace table prefix'.

write a script that will run RENAME TABLE for each table.

SELECT 
  GROUP_CONCAT('RENAME TABLE `', TABLE_SCHEMA, '`.`', TABLE_NAME, '` TO `', TABLE_SCHEMA, '`.`prefix_', TABLE_NAME, '`;' SEPARATOR ' ')
FROM 
  `TABLES` WHERE `TABLE_SCHEMA` = "test";

where "test" is expected database name

after this you can long query that will add prefixes if you execute it ;-)