Terminal attempts to load /bin/bash (or whatever the default shell for the user is). Since you moved that, it doesn’t know what to do unless you tell it where to look instead. There are several ways to override the default login shell in OS X, that don’t require a current working shell.
For a specific user:
System Preferences → Users & Groups → right click user → Advanced Options… → Login shell
For the current user:
Terminal → Preferences… → General → Shells open with: → Command (complete path)
For a specific Terminal profile:
Terminal → Preferences… → Profiles → ‹profile› → Shell → Run Command Also untick the “Run inside shell” box.
When you have a working shell, you can rename the binaries back to their originals and then use homebrew and use the same process to set /usr/local/bin/bash as the login shell. There is no need to replace binaries in /bin as the shell uses binaries from multiple directories using the PATH environment variable, including /usr/local/bin, which is the homebrew default install directory.