Ssh – OpenSSH use (public key or password) + google authenticator

I want to allow these two authentication types:
public key + google authenticator OR password + google authenticator.

I have the following in my sshd_config:

AuthenticationMethods publickey,keyboard-interactive:pam password,keyboard-interactive:pam
UsePAM yes
ChallengeResponseAuthentication yes
PubkeyAuthentication yes
PasswordAuthentication yes

And in the /etc/pam.d/ssh I uncommented

#@include common-auth and added auth required pam_google_authenticator.so

at the end of the file.

The key + token route still works, but for some reason my password always gets rejected with the message "Access denied".

I found out that whenever I set UsePAM to "yes", the password authentication fails. Not sure why?

Contents of /etc/pam.d/sshd: (this file seems very long for me but it was just the default for ubuntu, maybe I could shorten this down?)

# PAM configuration for the Secure Shell service

# Standard Un*x authentication.
#@include common-auth

# Disallow non-root logins when /etc/nologin exists.
account    required     pam_nologin.so

# Uncomment and edit /etc/security/access.conf if you need to set     complex
# access limits that are hard to express in sshd_config.
# account  required     pam_access.so

# Standard Un*x authorization.
@include common-account

# SELinux needs to be the first session rule.  This ensures that any
# lingering context has been cleared.  Without this it is possible     that a
# module could execute code in the wrong domain.
session [success=ok ignore=ignore module_unknown=ignore default=bad]            pam_selinux.so close

# Set the loginuid process attribute.
session    required     pam_loginuid.so

# Create a new session keyring.
session    optional     pam_keyinit.so force revoke

# Standard Un*x session setup and teardown.
@include common-session

# Print the message of the day upon successful login.
# This includes a dynamically generated part from /run/motd.dynamic
# and a static (admin-editable) part from /etc/motd.
session    optional     pam_motd.so  motd=/run/motd.dynamic noupdate
session    optional     pam_motd.so # [1]

# Print the status of the user's mailbox upon successful login.
session    optional     pam_mail.so standard noenv # [1]

# Set up user limits from /etc/security/limits.conf.
session    required     pam_limits.so

# Read environment variables from /etc/environment and
# /etc/security/pam_env.conf.
session    required     pam_env.so # [1]
# In Debian 4.0 (etch), locale-related environment variables were moved to
# /etc/default/locale, so read that as well.
session    required     pam_env.so user_readenv=1     envfile=/etc/default/locale

# SELinux needs to intervene at login time to ensure that the process     starts
# in the proper default security context.  Only sessions which are intended
# to run in the user's context should be run after this.
session [success=ok ignore=ignore module_unknown=ignore default=bad]            pam_selinux.so open

# Standard Un*x password updating.
@include common-password

auth required pam_google_authenticator.so

Contents of /etc/pam.d/common-auth:

#
# /etc/pam.d/common-auth - authentication settings common to all services
#
# This file is included from other service-specific PAM config files,
# and should contain a list of the authentication modules that define
# the central authentication scheme for use on the system
# (e.g., /etc/shadow, LDAP, Kerberos, etc.).  The default is to use the
# traditional Unix authentication mechanisms.
#
# As of pam 1.0.1-6, this file is managed by pam-auth-update by default.
# To take advantage of this, it is recommended that you configure any
# local modules either before or after the default block, and use
# pam-auth-update to manage selection of other modules.  See
# pam-auth-update(8) for details.

# here are the per-package modules (the "Primary" block)
auth    [success=1 default=ignore]  pam_unix.so nullok_secure
# here's the fallback if no module succeeds
auth    requisite           pam_deny.so
# prime the stack with a positive return value if there isn't one already;
# this avoids us returning an error just because nothing sets a success code
# since the modules above will each just jump around 
auth    required            pam_permit.so
# and here are more per-package modules (the "Additional" block)
auth    optional            pam_cap.so 
# end of pam-auth-update config

My question actually breaks down to: How do I use "UsePAM yes" together with "AuthenticationMethods password". Maybe I should delete this question and open a new one?