"But can it be proved that every starting value will generate a sequence that ends up with the cycle 4, 2, 1?" --

Can the proof be something in this line?
We have already proved that for any n=2^m the sequence ends up with the cycle 4, 2, 1. Now need to prove that for any sequence S(n), where n is the seed of the sequence, there exists a subsequence S(m) belonging to S(n) such that m=2^p for any integer p. If n is odd then the next number in sequence is 3n+1=2q for any integer q. q can be even or odd. If q is odd then the next to next of 3n+1 in sequence is 3q+1 which is again even. If q is even it can be either written as 2^x for some integer x, in which case we have reached our subsequence or it can be 2y for some integer y, in which case we need to again proceed as above.
Following this line of logic I think we could prove our subsequence statement above. Does it work?


P.S: BTW why can't I post directly on the blog?