How to protect against malicious web users sending tampered data?

At any point in this scenario, please let me know if there is a better way to handle this situation.

Let me prefix this by saying, I understand not to trust anything the client sends to you.. This is a question asking how would you do that.

Scenario: You have a user that is trying to update their address. This user has already created an account and already entered their address before. They load up the page and you send them all of the address information you have on them including there AddressId. So when they send this request back to you, with a completely new address: 123 Mary Lane Portland, OR 97123 is now 456 Candy Street Miami, Florida 33172.

This works great but say a malicious user updates their addressId in there browser to an id that doesn't belong to them and sends it back. This allows them to access any AddressId in the database.

I have come up with a few potential solutions.

Solution 1: Have a check on the server that verifies that whatever is passed back belongs to the logged in accountId.

Solution2: Pass the logged in users accountId to any stored procedure that is trying to update/create/delete information, thus allowing them to only manipulate their own data.

Solution3: Do a check in every stored procedure to make sure passed in ID belongs to that account.

Any elegant solutions out there that I haven't come across yet? Is embedding an ID in the page a bad practice?