alter table without 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