How to change RDS KMS Key without losing data?

With RDS this is easy. You will have some downtime that depends on the amount of data. For a small instance an hour, for a large instance set aside a day. The good part is that after your create the snapshot you can test independently without affecting your instance.

Everything is performed in the AWS RDS Console.

1) Create a snapshot of your RDS instance.

2) Copy the snapshot selecting a new master key.

3) Restore the instance or create a new instance from the snapshot.

Note: For items like this that modify data, I prefer to just create a new RDS instance. Verify everything and then shutdown the old instance.