Is there a way to check whether current user has certain permission via REST API? Preferably without using metadata APIs.
As far as I know, the Metadata API is the only way to do this. I don't believe it is possible to get that explicit setting via APEX, SOQL, or Describes.
The answer to this similar question sums up another option if you care more about the actual access to Objects rather than the explicit Modify All Data setting: https://salesforce.stackexchange.com/a/16533/411. In that case, you'd likely want to create a REST Endpoint that wraps some of that logic.
If I understand your question, you are asking if you remove the "Create" (or other) permission from a users profile (under "Custom Object Permissions") for a particular object, is there are way to check if the user can create that object via the REST API.
The answer is yes. You can use the REST API Describe call (/services/data/v28.0/sobjects/
<your-custom-object>/describe), and the results contain what you need - in this example, the "createable" property contains the "Create" permission from a users profile for this object. There is also, "deletable", "updateable", etc.