Changing startup accounts on alwayson setup
If you have local accounts and an AG then you must be using mirroring certificates - is this correct? If so then your switchover plan is likely going to be fine because nothing is going to change from the AG's point of view. 

I have done something similar just recently to replace local accounts and expiring AG mirroring certificates with service accounts and using that Windows authentication. After the local accounts were in place I ran Alter Endpoint Hadr_Endpoint For Database_Mirroring (Authentication = Negotiate) on both sides, followed by Alter Endpoint Hadr_Endpoint State = Stopped on each, and then started them again. I monitored the endpoint status from their DMVs to make sure they started and checking the ERRORLOG for issues, and confirmed that the AG dashboard was healthy. The final test to confirm it is a failover.

When you say using agent proxies didn't help though - are you sure you used one properly? What happened? I really would have thought it would work.