Is there a way that I can sort table rows by a specified column (e.g. username), reassign its it's primary key values and then replace the table content with the sorted values?
Yes, MySQL has a way to determine the table sorting of the rows in the file. If your table is a MyISAM type you can run:
ALTER TABLE `users` ORDER BY `username`;
The table will be now sorted by username. This will fix the order of rows in the file, the file itself might be fragmented in the filesystem, and you can't address that with an ALTER TABLE. From the manual:
ORDER BY enables you to create the new table with the rows in a specific order. Note that the table does not remain in this order after inserts and deletes. This option is useful primarily when you know that you are mostly to query the rows in a certain order most of the time. By using this option after major changes to the table, you might be able to get higher performance. In some cases, it might make sorting easier for MySQL if the table is in order by the column that you want to order it by later.
However if you mean that you want to rearrange a numeric primary key, so that the first user in the sorted list will have 1, 2 and so on, then, just don't do that. Never touch primary keys once assigned.