Absurdly, I've done it multiple times. It runs over SMS, literally any phone that can receive SMS' is already compatible.

I believe many of the messaging apps on Android also support exporting your messages as an archive, but no idea whether iMessage has any support for importing message history.