It is quite simple: if you want to go the "pure functional road", you need [purely functional data structures][1], which means immutable data structures, which in OO languages means immutable objects. 

For representing card decks, a very efficient, immutable structure is a stack, implemented as a single linked list (and not as an array!), maybe combined with a size counter. Then the typical stack operations like adding a card to the top, removing one from the top can be implemented as immutable operations like

      newCardDeck = oldCardDeck.push(newCard)  // oldCardDeck is not mutated

in O(1). Forward iterating over all elements can be implemented in O(N). Random access to a certain card will become an O(N) operation (instead of O(1) when using an array implementation), but most meaningful card operations can be implemented without the latter. 

> *the purely functional ways I can think of feel messy*

I don't feel so - using a stack abstraction is not necessarily more or less "messy" than using an array abstraction. If you can give a concrete example why you "feel" so, tell us, then we might be able to solve your problem.

However, if you are more used to classic OO modeling with mutable state, you can model and implement your card game using mutable classes (but then it won't very functional any more).




  [1]: https://en.wikipedia.org/wiki/Purely_functional_data_structure