How can I change my rescue e-mail address?

If you know the answers to your security questions then the instructions on the page that you posted from should work :

1. Navigate to appleid.apple.com using your web browser.
2. Click "Manage your account"
3. When prompted, sign in using your Apple ID and password.
4. Click Password & Security
5. You'll be asked to answer 2 of your 3 security questions before you can make any modifications. If you are unable to remember your answers, you can choose to send an email to your rescue email to reset your security questions.
6. After you've validated your identity by correctly answering your security questions, click Editto the right of your rescue email address.
7. Once you've finished editing your rescue email address, click the Savebutton directly below the email field.

If you don't know their answers then you will need to them reset first. If you have access to your old rescue email address then step 5 above should let you send reset info to it

If you don't have access to it, or don't have one, then see if this user tip helps you reset the questions: https://discussions.apple.com/docs/DOC-4551

e.g. you can try contacting iTunes Support : http://www.apple.com/support/itunes/contact/ - click on Contact iTunes Store Support on the right-hand side of the page, then Account Management , and then try Apple ID Account Security

or try ringing Apple in your country and ask to talk to the Accounts Security Team : http://support.apple.com/kb/HE57