encoded_char = urllib.quote(char, safe='~')

Now let's check it.
First, let's use their Perl to generate "golden" text to check against. It's important to name the script foo.pl to respect our ancestors.
$ cat foo.plMake the file 'golden.txt':
#!/usr/bin/perl
use URI;
for $idx ( 0 .. 255 ) {
print "$idx ", URI::Escape::uri_escape(chr($idx), "^A-Za-z0-9\-_.~" ), "\n";
}
$ ./foo.pl > golden.txtNow here's the Python:
$ cat foo.pyMake the test file:
#!/usr/bin/python
import urllib
for idx in range(256):
print "%d %s" % (idx, urllib.quote(chr(idx), safe='~'))
$ ./foo.py > python-test.txtTest:
$ diff golden.txt python-test.txtGood to go! If you try without the safe parameter, you'll see it doesn't encode '/' and does encode '~', which is what gave me the idea to try safe='~'.
$
Now go forth and prosper. If I work up the energy, I'll post a larger Amazon example in context.