The Java SDK for SQS automatically drops >256k messages into an S3 bucket and stores a pointer to the message in SQS itself. You set the bucket and the client transparently handles retrieving a message from SQS/S3 when necessary.
Based on the structure of the message (UUIDv4) you could probably roll your own implementation in any language.