Yes, I have a setup where I can ssh to my server using public key authentication, with a fallback to two-factor authentication with Google Authenticator + password when my private key is not available. These are the steps I used to set it up.
Installing Prerequisites
My server is running Ubuntu Lucid Lynx (10.04), and the default repository for that distribution only provides Mercurial 1.4. I found out that I needed at least Mercurial 1.5 to clone the repository for Google Authenticator. I needed to add a new repository to get the latest version Mercurial.
$ sudo aptitude install python-software-properties
$ sudo add-apt-repository ppa:mercurial-ppa/releases
$ sudo aptitude update
$ sudo aptitude install mercurial
The Google Authenticator repository includes an external Subversion repository, so I needed to install Subversion, too. There were a few other dependencies I needed to compile and install Google Authenticator as well.
$ sudo aptitude install gcc libpam0g-dev subversion
Downloading and Installing Google Authenticator
Now I was ready to download Google Authenticator and install it on my server.
$ hg clone https://code.google.com/p/google-authenticator/
$ cd google-authenticator/libpam/
$ make
$ sudo make install
Configuring sshd
I opened /etc/pam.d/sshd and added the following line at the top:
auth optional pam_google_authenticator.so
I opened /etc/ssh/sshd_config and changed one line. The existing line was
ChallengeResponseAuthentication no
and I changed it to
ChallengeResponseAuthentication yes
Configuring Google Authenticator for Your Account
The next step is to turn on Google Authenticator for your account. You do this by simply running:
$ google-authenticator
Make sure you run this as the user who will be making ssh connections, not root. Make a note of your new secret key and your emergency scratch codes. The wizard will ask you several questions to configure the security settings for your account.
Configuring Your Mobile App
I use the Google Authenticator app for iPhone. This app has a [+] button that allows me to add a new Time Based Token using the secret key I obtained from the google-authenticator command on my server. It was trivial to set up. I can't help you with apps on any other platform, but I imagine the process is equally simple.
Pulling the Trigger
The last thing you need to do is restart sshd.
$ sudo /etc/init.d/ssh restart
At this point, when I try to connect to the server when my private key is available, authentication just works. When my private key is not available, I get a prompt for a verification code, then my account password.
Bingo, two-factor authentication.