Is there a way to generate random passwords in Safari, without iCloud?

No there is no way in Safari directly,

You can only go directly to the Keychain
(Spotlight -> Keychain // or via the Finder -> /Applications/Utilities/Keychain.app)

and create a new Key (CMD+N).

You will get the window with the little key icon and when you click on it, it will show you a little popup with the Password Assistant.

One can always keep a sign-up form with a displayable password field close at hand, for instance Google's. Save the link to Bookmarks > Favorites. Then when it's time:

1. Visit the site
2. Use Safari to suggest a password
3. Toggle password visibility
4. Copy the text

When using the process proposed by @Felicio, I have also noticed that you cannot see (or copy) the entire generated password. The following steps will let you see all of it, but you still can't copy it until after it gets saved in the keychain.

1. Visit the site's registration form
2. Click in the Password box to get Safari to suggest a password
3. Click "Don't Use"
4. Click the key icon in the Password box
5. The popup shows the entire generated password following "Fill Password Again:" along with letting you pick a new one
6. At this point, I usually save a screenshot to my desktop to temporarily save the generated password just in (the rare) case that Safari doesn't successfully save the password to the keychain.