It's currently at system menu 4.0U. Should I add homebrew or upgrade first? If I add homebrew first, can I upgrade safely and reinstall the homebrew?

I would say upgrade first, you can indeed install homebrew afterwards.