Use a later action hook
You cannot use Conditional Tags before the posts_selection hook has run (as per the codex), which happens right after pre_get_posts and quite a bit after init.
Hence, would it not be easier to set the cookie at a later stage of the request, rather than attempting to detect the 404 earlier (which, off the bat, I would not know how)?
The wp action, for instance, should be early enough.
If I understand you correctly, you should basically be able to set the cookie at the very end of the request, since it becomes relevant on the following request only anyway.
[Further Info] How do Conditional Tags work?
Conditional Tags depend on the query object’s (instance of WP_Query) public “query type” boolean properties, which by default are set to false (see wp-includes/query.php, Lines 1008 ff. [as of 3.5.1]).
These properties are populated with the correct values in WP_Query‘s parse_query method, which runs right before pre_get_posts (see wp-includes/query.php, Lines 1907 ff. [as of 3.5.1]).
Hence, even though the codex suggests differently, Conditional Tags should (not vouching for it, though) actually already be usable in pre_get_posts callbacks.
Definitely not earlier though – init is out of the question.