There is no requirement to use GND and PWR for the internal layers. That seems to be a commonly repeated recommendation, but isn't necessary.
Most of the 4-layer PCBs I tend to make have both inner layers as ground planes to allow high-frequency routing on the outer layers, and then when not required to form an unbroken plane, get chopped up to use for power and signal routing as required. You can also route ground and power on outer layers too.
Basically, you can use all layers as required, don't feel that you can only use one layer for just power, or just signals.
I see a suggestion for using one layer for horizontal and one layer for vertical traces, however this is again a case of "that was then, this is now". Its a useful starting point for simple boards, however when you start using predominantly surface mount components, and throw into the mix high speed signals or fast edges, the concept rapidly falls apart.
My approach is as follows:
- Start by placing key components - connectors, large ICs, etc.
- Work out where the power pins of each IC are, and make sure decoupling capacitors are given priority nearby (e.g. a pull-up resistor for a switch can go anywhere, so don't let it displace a decoupling cap).
- Lay some preliminary power planes, or at least vias to allow routing of planes on other layers if need be.
- Route any high speed signals (differential traces, USB, RF traces, etc) if any. These are the most tightly controlled constraints, so must be given preference. Make sure that these have an unbroken plane underneath them along their entire journey. The plane would preferrably be ground, but can also be power so long as you have sufficient decoupling capacitors at each end from power to ground to allow return currents to jump on to the plane.
- Route any analogue components - with this, seperating analogue and digital ground planes is not necessary and can be harmful. The main idea is to seperate analogue and digital circuitry - you don't want return currents from your digital components running under your sensitive analogue or RF components.
- Place any less important components where there is room for them, but try to keep them grouped with components that they belong to. For example don't place a pull-up resistor on the opposite end of the board from all the other parts that trace connects to.
- Route the second most important signals, starting with any parallel buses that want similar routing or length, along with buses like JTAG or SPI.
- Begin to fill in your power planes based on your preliminary paths from step 2. You will likely find these have to move around as you've gone along.
- Route the remainder of the signals - e.g. buttons and low speed signals can route pretty much wherever, the number of vias in such traces don't matter to much, so they can jump around to avoid everything else.
I also tend to route from both ends - with the components grouped together like little cities, you can route traces within each city as needed, and try to escape signals which share a common destination out of each city like little highways. These can then be connected up afterwards.
The thing to bare in mind is this is an iterative process. Keep looking at the whole picture to see how each chunk of the board is likely to connect up.
Don't be afraid to move traces and components as you go along. You might discover that if you rotate a chip or reorganise some of the blocks that the routing begins to untangle.