The very first people to domesticate the horse did so with just stone technology. Our best evidence (there's some contention) points to horses being domesticated by the Botai culture of modern day Kazakhstan, between 4000 and 3500 BCE. We think horses were only domesticated once, so no other culture actually fits your criteria of having not been introduced to them from elsewhere!

The Botai culture were most definitely "horse-people", but not in the sense of being nomadic pastoralists like the familiar Scythians, Mongols, etc. Nomadic pastoralism has three elements: horse-riding, wheeled vehicles and herding (animals other than horses), and the Botai culture only had one of them. They kept horses mainly for food—milk and meat—and in the early stages of domestication may even have ridden horses to hunt other horses. Essentially they were "horseback hunter-gatherers" – the first and last until horses were introduced to the Americas and enthusiastically adopted by peoples like the Comanches.

Horses spread from Botai to other parts of the steppe at the tail end of the Stone Age. Horse remains crop up in the later phases of Neolithic steppe cultures like Sredny Stog, Khvalynsk and Dnieper-Donets. Again they were used mainly for food, and in particular for special feasts at occasions like funerals, suggesting they were seen as an exotic import rather than the staple food source of the Botai culture. Horses didn't really take off on the steppe until they were paired with wagons in the Yamnaya horizon (starting 3400 BCE), creating the earliest form of nomadic pastoralism, but by that time bronze metallurgy had been introduced to the steppe.