There are different opinions on using FULLSCAN. I for one have been burnt by sampled statistics why I tend to favour them. On the other hand, yes, they do take a long time. What you can consider is
UPDATE STATISTICS WITH FULLSCAN, INDEX
to only perform the update on indexes. This is a lot faster than updating statistics for non-indexed columns, not the least because SQL Server scans the table once for each column.
You may also investigate on which tables you really need fullscan, but this is certainly tedious to find out.