Hey Matt.
How well insulated are the walls?
How about the roof?
What about the door, assuming there is one?
Usually you loose most heat through the roof, then walls, then windows and doors.
Could you get under the floor and insulate between the battens/beams? A couple of inches of insulation could do a lot.
I understand you don’t want to cut up your freshly built shed, so adding another layer to the existing floor sounds like a good idea to me.
Clay and perlite won’t help much as you say.
How about cork (or wood fiber, let’s say 1,5 “) and a thin layer of wood or laminate or whatever (.5” or less)?