How to deploy changes to staging database while still keep it in sync with production master database?

You can't.

My suggestion is to not replicate production to staging, but to occasionally rebuild the staging database with one of your production backup files. Then you're working with production data (albeit a few hours or days old) but changes you make on staging won't affect production.

EDIT: With your edit, this is now a significantly different question.

If you have beta testers using your staging server and expecting their data to roll into production, it's not a staging server: it's a production server. I think that's the fundamental concept shift making this difficult to answer; most of us (I think) consider a staging server to be an etch-a-sketch that can be dumped and rebuilt without fear. If you're planning to allow some users to beta-test your changes and retain their data when you roll into production, you need a different framework than staging/production.

EDIT2: Here are some Stack Overflow questions that deal with this sort of setup:

• Gem that makes it easy to roll out features to a subset of users
• Best practices for limited feature rollout (this one is interesting because it mentions the difficulties of database merging in particular; it looks like a known-difficult problem)