This requires that you have access to another Windows computer with an Internet connection. You'll be installing and updating Malwarebytes on that computer, and then copying the up-to-date data folder via USB drive (or similar) to the computer that lacks Internet or is in Safe Mode.

Step 1
If you haven't yet, download the Malwarebytes installer (www.malwarebytes.org, free download, mbam-setup), install it onto the safe PC, and run it to update the database. When you're done, copy the mbam-setup exe to your USB drive if you haven't already installed Malwarebytes on the PC that lacks Internet.

Step 2
While still on the safe PC, find the "Malwarebytes" folder that resides in the "ProgramData" or "Application Data" folder:

For Windows Vista & 7:
C:\ProgramData
For Windows XP:
C:\Documents and Settings\All Users\Application Data
Copy the "Malwarebytes" folder to your USB drive, then delete the contents of the "Logs" and "Quarantine" folders that are inside the "Malwarebytes Anti-Malware" folder on the USB drive.

Step 3
Go to the PC that lacks Internet or is in Safe Mode. Install Malwarebytes from the mbam-setup if you haven't yet. Now find the "Malwarebytes" folder on this PC (refer to step 2 for the location) and delete it. Copy over the updated folder from the USB drive to where the deleted one used to be.

Malwarebytes should now have the latest update data, and you can verify it by launching the program.