While I appreciate Kevin Reid's answer, it was at a level that was higher than what my question was asking. Understandably with out knowledge of Bullet Physics, it'd be hard to answer this question. I got this working and have an answer that is specific to Bullet Physics.

Along with extending the RigidBody class like I mentioned in my question. I also needed to extend the CollisionAlgorithm class. This is mostly to override the processCollision() function. Inside the processCollision() function (which takes the two colliding bodies as arguments), I was able to create a cube shape and appropriate Transform for the cube that my entity was currently colliding with. Then just let the default collision happen based on the entity and the specific cube/cubes it's colliding with. In order to use the newly extended CollisionAlgorithm, I needed to register the algorithm to deal with the shapes I want it to handle. In this case that's pretty much the terrain type against everything else. For that I used registerCollisionCreateFunc() with my CollisionDispatcher.

So for those following along in the future:

1. Extend RigidBody to have a basic collision check with your terrain.
2. Create a instance of your RigidBody class and add it to your DynamicsWorld or whatever PhysicsProccesor you're using.
3. Extend CollisionAlgorithm, specifically processCollision() to create Bullet Physics shapes and Transforms that match with your collision location.
4. Register your version of CollisionAlgorithm with your CollisionDispatcher using registerCollisionCreateFunc(). (This registration is done multiple times, once for each pair of shapes you want to collide.)

EDIT

Here's a video of it in action if anyone is interested.

While I appreciate Kevin Reid's answer, it was at a level that was higher than what my question was asking. Understandably with out knowledge of Bullet Physics, it'd be hard to answer this question. I got this working and have an answer that is specific to Bullet Physics.

Along with extending the RigidBody class like I mentioned in my question. I also needed to extend the CollisionAlgorithm class. This is mostly to override the processCollision() function. Inside the processCollision() function (which takes the two colliding bodies as arguments), I was able to create a cube shape and appropriate Transform for the cube that my entity was currently colliding with. Then just let the default collision happen based on the entity and the specific cube/cubes it's colliding with. In order to use the newly extended CollisionAlgorithm, I needed to register the algorithm to deal with the shapes I want it to handle. In this case that's pretty much the terrain type against everything else. For that I used registerCollisionCreateFunc() with my CollisionDispatcher.

So for those following along in the future:

1. Extend RigidBody to have a basic collision check with your terrain.
2. Create a instance of your RigidBody class and add it to your DynamicsWorld or whatever PhysicsProccesor you're using.
3. Extend CollisionAlgorithm, specifically processCollision() to create Bullet Physics shapes and Transforms that match with your collision location.
4. Register your version of CollisionAlgorithm with your CollisionDispatcher using registerCollisionCreateFunc(). (This registration is done multiple times, once for each pair of shapes you want to collide.)

EDIT

Here's a video of it in action if anyone is interested.

Detecting the initial collision

For my initial collision checks, my extended rigidBody overrides the checkCollideWith function described in my question. I have a function for my terrain that can check if the world is solid at a specific point. Basically, I test my terrain against the object being passed in by the checkCollideWith function, seeing if my terrain is solid anywhere within the bounds of that object.

Now, there's also the next step in Bullet, finding the contact points. This takes place in the processCollision() function I mentioned above. Here, I've made a boxShape the size of a terrain cube, then when I detect a collision in the checkCollideWith function, I place that terrain cube sized boxShape at the collision location, and let Bullet use all it's default algorithms for detecting collision points there.

So basically, if a physics objects bounds touch solid material. I'll place my temporary physics body to that location and tell Bullet to check collisions against that temporary cube, as if it were always there. This is sort of like super optimizing placing a boxShape for every cube in my terrain. Instead of millions of boxShapes, I only need to have one that teleports around when a collision is detected.

While I appreciate Kevin Reid's answer, it was at a level that was higher than what my question was asking. Understandably with out knowledge of Bullet Physics, it'd be hard to answer this question. I got this working and have an answer that is specific to Bullet Physics.

Along with extending the RigidBody class like I mentioned in my question. I also needed to extend the CollisionAlgorithm class. This is mostly to override the processCollision() function. Inside the processCollision() function (which takes the two colliding bodies as arguments), I was able to create a cube shape and appropriate Transform for the cube that my entity was currently colliding with. Then just let the default collision happen based on the entity and the specific cube/cubes it's colliding with. In order to use the newly extended CollisionAlgorithm, I needed to register the algorithm to deal with the shapes I want it to handle. In this case that's pretty much the terrain type against everything else. For that I used registerCollisionCreateFunc() with my CollisionDispatcher.

So for those following along in the future:

1. Extend RigidBody to have a basic collision check with your terrain.
2. Create a instance of your RigidBody class and add it to your DynamicsWorld or whatever PhysicsProccesor you're using.
3. Extend CollisionAlgorithm, specifically processCollision() to create Bullet Physics shapes and Transforms that match with your collision location.
4. Register your version of CollisionAlgorithm with your CollisionDispatcher using registerCollisionCreateFunc(). (This registration is done multiple times, once for each pair of shapes you want to collide.)

While I appreciate Kevin Reid's answer, it was at a level that was higher than what my question was asking. Understandably with out knowledge of Bullet Physics, it'd be hard to answer this question. I got this working and have an answer that is specific to Bullet Physics.

Along with extending the RigidBody class like I mentioned in my question. I also needed to extend the CollisionAlgorithm class. This is mostly to override the processCollision() function. Inside the processCollision() function (which takes the two colliding bodies as arguments), I was able to create a cube shape and appropriate Transform for the cube that my entity was currently colliding with. Then just let the default collision happen based on the entity and the specific cube/cubes it's colliding with. In order to use the newly extended CollisionAlgorithm, I needed to register the algorithm to deal with the shapes I want it to handle. In this case that's pretty much the terrain type against everything else. For that I used registerCollisionCreateFunc() with my CollisionDispatcher.

So for those following along in the future:

1. Extend RigidBody to have a basic collision check with your terrain.
2. Create a instance of your RigidBody class and add it to your DynamicsWorld or whatever PhysicsProccesor you're using.
3. Extend CollisionAlgorithm, specifically processCollision() to create Bullet Physics shapes and Transforms that match with your collision location.
4. Register your version of CollisionAlgorithm with your CollisionDispatcher using registerCollisionCreateFunc(). (This registration is done multiple times, once for each pair of shapes you want to collide.)

EDIT

Here's a video of it in action if anyone is interested.