rlwrap can be used (and not just for psql!)

Yes, rlwrap is very good.
But unfortunately it breaks autocompletion, so it's not a full substitute for readline.
I guess for the time being the real "solution" is for everybody to recompile their own psql against readline and openssl.

# apt-get build-dep postgresql-client-9.0
$ apt-get source postgresql-client-9.0
$ cd postgresql-9.0-9.0.3/
$ fakeroot-sysv debian/rules binary
# dpkg -i postgresql-client-9.0_9.0.3-1_amd64.deb