I would go with the update cursor (especially at 10.1). In my experiences, update cursors are about waaaay faster than the field calculator or Calculate Field tool. I used to have a script that would run 6 field calculations on a table with only 20,000 records that used to take about 15 minutes. With update cursors (and dictionaries) the execution time is down to just under a minute. You won't be able to use dictionaries with an update cursor on a table with 1.5 billion records, but I think using an update cursor by itself will definitely work much faster than field calculations.