Form element's #required set to FALSE, but form submission still consider it as required
Yes, theming the form only changes its markup. If you want to change the form you have to hook_form_alter. 

I once wondered how to add required styles to elements that weren't actually required. Your question just gave me the answer.