> ここで、 cat_1st をキーとしてソートしたいのですが、
> 単純に ASC や DESC でソートするのではなく、
> 特定の順番で並べたいと考えています。
>
> 例: 'P' → 'A' → 'N' → 'C' → ... → 'NO'
>
> このようなソートを、MySQLだけで実現できるのでしょうか？
>
> 上記のように並べたいのは、 cat_1st のそれぞれの値の重要性や、
> 使用頻度などによるものです。
> ただ、このソートは必須ではなく、「あまり手をかけずにできれば」という程度なので、
> このためにカラムを1つ（重要性などを表す数値など）増やす、
> などは考えておりません。

「特定の順番」をRDBMS側に指示する必要がある訳ですから、検索SQL中でCASE式などで与えるか、事前に順序を保持した表や列を作っておく必要があります。

「順序を示す列を持つ」ということが、「手を掛ける」という程のことなのかは考え方次第ですが、基の表をいじりたくないということなら、別の表にして保持してはどうでしょうか？

-- 順序保持の表
create table sortseq
(cat_1st    varchar(10),
 seq        int)
 CHARSET=latin1;

-- 順序を設定
insert into sortseq values('F',1);
insert into sortseq values('A',2);
insert into sortseq values('N',3);
insert into sortseq values('C',4);
insert into sortseq values('NO',999);

-- 検索
select e.* from example as e
 inner join sortseq as s
  on e.cat_1st=s.cat_1st
 order by seq
;

データ件数が数千件以上といった数なら、cat_1st列、seq列に適切なインデクスを定義すれば、ジョイン及びソートによるオーバーヘッドも抑止できると思います。
_________________________________________________________________
Live Search 地図検索で東京の都心部が3D表示に！ドコをみてみる？
http://maps.live.com/