1. Can you do it without a plugin?
Certainly. Anything a plugin can do, you can obviously also implement yourself.
1.1 Should you do it without a plugin?
No. This is clearly plugin-territory. Even if you want to write the plugin yourself, this would be a better fit for a custom plugin than to incorporate it in your theme. That’s a matter of preference and opinion though – of course it can be done within your theme also.
For the sake of completeness, let me mention Jeff Farthing’s theme-my-login. It’s a well written, powerful plugin that has been developed for years. It is for sure the (much) less work-intensive solution and you should at least consider using it before you hack away on writing something similar (and most likely less powerful).
2. How can it be done?
Have a look at the Administrative Actions and hook into those.
Again consider downloading the above mentioned plugin and dissect how it works.