Most changes would still block, yes, but at least in PostgreSQL many changes will only block a short time (since they do not require a full table rewrite, only altering the table descirption) and in my experience rewriting a table is generally quick for a decent sized database (tables with a handful of millions of rows).
Only ever done this in MySQL, where you really can't alter big, live, tables. Well, facebook made an utility for it: http://www.facebook.com/notes/mysql-at-facebook/online-schem...