VCC on surface or inner layer on 4-layer board?
I would say it is not reasonable if you want two outer signal/component layers because what are you going to do with the two inner layers? Make them both ground planes? It's a much bigger waste than just using stitching caps. You might as well go with a 2 layer board and deal with a similar level of routing difficulties but with greatly reduced cost

You can try to locate your vias near pre-existing decoupling caps if possible.

However, if you are going to place all components on one layer, you could just go signal/component-gnd-signal-pwr. The ground plane is now the reference layer for both signal layers due to adjacency. No more stitching caps to worry about and you still have two signal layers so you can criss cross with no origami required. Plus that inner signal layer is shielded. What more could you want?