How to "paint" a mesh on a stl/obj I have almost 0 experience in 3d modeling and I'm looking for a simple way to color a model. 

I want to replicate this paint job of a model.

I've tried Blender, tried Mudbox and I don't have the money for Mari which is the software being used in the video.

The issue with both is that it seems to take forever to try and paint them. It's a high-poly model with a bunch of vertices. Both programs seize up and hang and I'm forced to quit them.

How can I simply and efficiently color the model to get it ready for sandstone color printing?
If you've looked into using Blender, you would have discovered that that program is free. It is also one of the better suited programs available for the task you've selected. 

It's possible that your search terms may not have provided the best results for your objective. The task you describe is known as UV mapping, also known as adding texture to mesh, adding texture to a model. The generic term "texture" can be confused, as many people would consider texture to be the feel of a surface. Rough, smooth, slippery, etc., do not apply here.

Texture in the 3D modeling world applies to a surface description specific to visibility. In your task, texture refers directly to color.

Consider to search using the above terms or follow this lead:
Add texture to model Blender

Doing so provided a few quite well written links. One of the first to appear is an Instructable.

The above Instructable also links to a video, which is also a good location for learning basics for Blender and texturing models.

The above search also results in finding an SE entry directly related to Blender:
StackExchange Blender texture Q/A

Consider that you can create a flat image using your preferred graphics editor, placing shapes and colors as needed and then "project" or paste or plaster or project that image on the surface of the model in a controlled manner. This would be easier and faster than attempting to color manually individual triangles of the model's mesh. The SE link summarizes this process, although additional research is indicated.

Practice with Blender on simplified models and you should be able to grasp the necessary skills in short order.