I used to do a fairly hard style of kung fu, and we learned to roll and breakfall on concrete. As folks already mentioned, it's mainly a matter of working on it very slowly and carefully. It's a bit of a different skill than just having a really smooth roll on the mat, so go ahead and practice on a semi-hard surface, as Virgil says.
Unfortunately I have kind of lost the knack due to lack of practice, but for a while there I could comfortably take a medium-hard hip throw or a surprise leg sweep and the fall didn't hurt at all. A full-speed aikido throw from a vigorous attack would be a different story, but I imagine you can probably get to that level over time.
I should also mention that we always had a good supply of Chinese bruise medicine handy for this and other conditioning-type exercises