This answer intends to give a possible way for satisfaction of the main question: Secure an Ubuntu OpenSSH server from Brute force attacks but without a firewall or SSH key pair?
Actually I prefer to use Firewall and SSH key pair and found the answer provided from Doug Smythies for really useful.
Protect SSH With Two-Factor Authentication
Two-factor authentication (2FA) is a type of multi-factor authentication. In this example 2FA confirming a user's claimed identity by utilizing a combination of these two different components:
Time based, six digit token code - authentication code. By default, these tokens are good for 30 seconds plus additionally added 60 seconds in order to compensate for possible time-skew.
User's password, which itself should be secure enough.
Actually when you have set PermitRootLogin no
and the usernames are good chosen, for me, this method can be called 3FA.
Additionally, if the computer that you are logging into isn't hardened against brute-force login attempts, you can enable rate-limiting for the authentication module.
Let's begin:
1. Install dependencies
sudo apt-get install libpam-google-authenticator
2. Edit the configuration files
Edit /etc/pam.d/sshd
and add this directive:
# Google Authenticator
auth required pam_google_authenticator.so
Add it in the beginning of the file. In this way the system will ask first authentication code and only then will ask password. Add it in the end of the file - system will ask first password.
Edit /etc/ssh/sshd_config
and modify or add these directives:
ChallengeResponseAuthentication yes
UsePAM yes
PasswordAuthentication no # You can leave this 'yes' it doesn't matter.
3. Activate the two-factor authentication for a user
Switch to the user who should use the two-factor authentication and type in the terminal:
$ google-authenticator Enter
Do you want authentication tokens to be time-based (y/n) yEnter
https://www.google.com/chart?chs=200x200&chld=M|0&cht=qr&chl=otpauth://totp/user@host%3Fsecret%3DE3CY3TNSNBXXXXXX
Your new secret key is: E3CY3TNSNBXXXXXX
Your verification code is 229999
Your emergency scratch codes are:
19999711
...
Do you want me to update your "/home/user/.google_authenticator" file (y/n) yEnter
Do you want to disallow multiple uses of the same authentication token? This restricts you to one login about every 30s, but it increases your chances to notice or even prevent man-in-the-middle attacks
(y/n) yEnter
By default, tokens are good for 30 seconds and in order to compensate for possible time-skew between the client and the server, we allow an extra token before and after the current time. If you experience problems with poor time synchronization, you can increase the window from its default size of 1:30min to about 4min. Do you want to do so
(y/n) yEnter
If the computer that you are logging into isn't hardened against brute-force login attempts, you can enable rate-limiting for the authentication module. By default, this limits attackers to no more than 3 login attempts every 30s. Do you want to enable rate-limiting
(y/n) yEnter
This dialogue will generate an authentication file called .google_authenticator
placed in the user's home directory. This file can be used also for other user's accounts if you want all of them to use same tokens. Further this file can be customized and also can be used for 2FA within Apache2, but that's another story.
4. Generate authentication codes
The secret key - E3CY3TNSNBXXXXXX
- generated in the above step is used for authentication codes generation within some application as:
5. Example of usage
In this example is used the Authenticator extension for Chromium/Chrome:

6. Further reading
EDIT:
In some cases there could has a difference between google's clock and the server's clock. Here you are few tips according this issue:
Unfortunately: If it's a VPS, you may not have permissions to do this... If you are using a VPS, contact your provider to handle this for you.
In case if your provider doesn't want to response to your requirements, the above set-up will work but with time-shift. Type date
in your server's console and measure this time-shift. Then just work with this time-shift between the moment of authentication code generation and the moment of its use.