Add serial in specific order?

I have ~25 columns in my database and need to order the rows by all
columns to do queries like:

SELECT a FROM table ORDER BY a, b, c, ...., z;

I suspect it would be highly ineffective to order by all columns for
every query! Hence I'd like to do the ordering only once and add a
serial to the database specifying the order so all subsequent queries
can be done like:

SELECT b FROM table ORDER BY added_serial;

The optimal ordering is found from analysis of the database and is not
known at build time. Is it possible to add the serial without having to
rebuild the database? It has millions of rows, by the way...

Thanks for any advice.

Poul Jensen