Posso ter uma chave primária sem índice clusterizado? Também posso ter índice clusterizado com vários valores?

(Esta resposta é apenas para SQL Server 2005+. Não sei nada sobre MySQL.)

Sim. Como você mencionou, uma restrição de chave primária é apoiada por um índice clusterizado por padrão. Você pode dizer ao SQL Server para apoiar a restrição com um índice não clusterizado declarando a restrição da seguinte maneira:

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

Sim, você pode definir um índice com mais de uma coluna na chave de índice. Na verdade, não é diferente de um índice não clusterizado.

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

Referências:ALTER TABLE , CREATE INDEX