Yes, I would say that chunking the queries as you mentioned would be your best bet. Ordinarily, the quickest thing to do would be to do this with a combination of OFFSET and LIMIT on conjunction with ORDER BY to define the chunks, but using really large ordered OFFSET values can be a performance issue unto itself (since it has to compute the whole order first, and then due the LIMIT and OFFSET), especially given the number of records you have in the table.
However, since you stated that you already have them partitioned via a hash value that you can uniquely iterate over, I would simply go with that as the chunking mechanism -- it's built in, and should give you much smaller chunks to work with. You could consider subdividing those chunks further via the mechanism I mentioned earlier if they are still too large to perform well.
Note that you may need to have indexes on the hash column so it will be able to find them quickly, although from a pure Postgres perspective they may not be used if the query planner decides too many rows will need to be returned (and Redshift may have additional differences).
To optimize it further, you could consider multi-threading it to do multiple updates at once. I often use the GNU parallel tool for this, since it allows for quick and easy multithreading of shell commands. This could be used in conjunction with the psql client, which, near as I can tell, is supported in Redshift.
Note:
Ultimately, I think the best overall bet would be to have separate tables for each first-character of the hash value, each of which inherits from a master table. That makes it so that each table can be dealt with individually in an UPDATE without having to go through a large filtering operation first, etc., but you can still query all of the tables using the parent table (i.e. it shouldn't really impact existing SELECT statements).
However, that is certainly a larger undertaking that may not be feasible to do right now, and if you were to do such a thing, you'd want to verify with the query planner, etc. that it really is an improvement and that there are no Redshift specific reasons that this isn't a good idea (I'm speaking purely from a Postgres perspective).