The old-school way to do this is to use linked lists for sequential data and sets, and alists (association lists, list of key-value pairs) for hash-maps. These do not have the correct performance characteristics, but are functional, and, for small data, they are good enough.
You can wrap these in structs to provide a clojure-like interface in the meantime before you can get your hands on proper persistent data structures. Fortunately, there’s a lot of implementations of radix tries, relaxed radix tries, hash array mapped tries, and friends in both scheme and C and C++.