I'll answer the second question even if nightcracker correctly stated that PKI isn't bound to integer factorization per se.
To look for symmetric encryption protocols for authentication you do not have to look further to the market for public transport cards and access cards. Many of these systems rely on a chip card that just rely on random and symmetric operations. A well known example of this is the MIFARE range of products.
With these systems, a lot of security depends on the back-end. For instance, abused or cloned cards could be black listed - which is comparable with revoking a certificate in a PKI scheme. Note that it would be trivial to make cloned cards once the master keys have been compromised.
From a cryptographic point of view, it is much better to rely on PKI than any symmetric scheme for large scale authentication. Secure key management is much harder for symmetric schemes than for PKI. Even if standard RSA and DH have been broken, you really don't want to rely on shared secrets for your key management scheme.