Would changing the permissions implemented by a module require a new version of the module? I have created a module, and I have to change the permissions implemented (and used) from the module. Should I create a new major version (e.g. passing from 7.x-1 to 7.x-2), or is it fine to create a minor version (e.g. passing from 7.x-1.3 to 7.x-1.4)?

I am talking of a module for which there is already an official release, not of a module that has only a development snapshot.
If it changes significant behaviour from previous version I recommend changing the major version. Even if its just a single adjustment like permissions. Wrong or missing permissions may cause huge problems on a site running your module.