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.