クラスタ化インデックスなしで主キーを持つことはできますか？また、複数値のクラスター化されたインデックスを持つことはできますか？

（この回答はSQL Server 2005以降のみを対象としています。MySQLについては何も知りません。）

はい。おっしゃるように、主キー制約はデフォルトでクラスター化インデックスによって支えられています。次のように制約を宣言することにより、非クラスター化インデックスで制約をバックアップするようにSQLServerに指示できます。

ALTER TABLE MyTable
    ADD CONSTRAINT PK_MyTable
        PRIMARY KEY NONCLUSTERED(Col1);

はい、インデックスキーに複数の列を含むインデックスを定義できます。クラスター化されていないインデックスとまったく同じです。

CREATE UNIQUE CLUSTERED INDEX IX_MyTable_Clus
    ON MyTable(Col1, Col2, Col3);