alter table without an ACCESS EXCLUSIVE lock

Hi,

i'm searching for a solution for changing the type of a column, e.g. from varchar(128) to varchar(512), without an ACCESS EXCLUSIVE lock. The issue is that the relation is nearly 100 million rows big and in our environment every second of downtime is very bad.
In my current setup a slave database is replicated via skytools, so changing the relation first on slave, make a master / slave change and then do the alter table on the other database is one solution for a minimum downtime. But with postgres 9 I will use wal shipping for replication and here is the problem. On slave I have just read permissions and if I do the alter table on the master db a downtime is occuring and this is what I have to avoid.

regards,
Andi