There is a TOTP/Google Auth 2FA application for J2ME, which will run on many feature phones: http://totpme.sourceforge.net/
In addition, 2FA systems are not limited to devices the consumer already has -- Paypal could easily send you a device that generates a one-time password, or that uses a challenge-response protocol to do so.