One method I used (in a geometry application not a game) was to traverse the mesh using depth/breadth first search and extract each connected component to a separate mesh . This will give you nice results as far as your mesh is composed of parts that are not connected.
The problem though is that if your mesh is connected this doesn't work.
The other method I can think of is you can generate a 3D grid based on the shape and the size of the mesh, and split the mesh based on the distribution of the vertices, the problem; this will look ugly and unnatural.
What I recommend is combining the two methods above. So the first algorithm will split the mesh into parts and the second one to split each part to uniform number of sub-parts and you can iterate until you get satisfactory results. The problem though "realistic results" is something very hard to do without any human input, so I recommend there are some constraints put by the guy who will make the models for each model, this way you will get some randomness from your algorithm while getting more "realistic results" because of the constraints.
You can also combine some kind of real time constructive solid geometry with the other methods but that might be kind of hard to implement.
Well, most of the models I worked with were exported from CAD applications and were nicely connected (as they would be in real life), so your best bet might be to design your models with this in mind, but anyway you may want to use some kind of tolerance or graph radius; for example if a certain component has graph radius less than K you don't make it a separate part.
You can also use some geometrical attributes of your mesh (as the traverse only use topological properties) one might be using a tolerance; sometimes a vertex will be duplicate (you have two vertices that have the (almost) same value), in a naive BFS they might be treated as disconnected, in real world though, you may want to "merge" them which might not be good for rendering, in this case you need to merge them only when dealing with connectivity issue and not in the vertex buffer that is going to be rendered.