How can I check tire pressure without a pressure gauge?
Unless you have got correctly inflated tyres then you do not know what you are missing. No rule of thumb can make up for this. Tyre inflation is really important and your best bet is to get a track pump with valve to check your tyres with. Do this every fortnight, leave it to every month if your journey times are not important to you. I cannot stress enough the importance of getting a track pump, however, that is not what you asked.

Several answers here have mentioned that you should take a peek at how much your tyres splay when you are riding the bike. This is definitely a useful check, however you must bear in mind that a correctly inflated tyre is not a solid tyre and it will bulge out sideways anyway. Only when drastically under-inflated will it show an easily discernible extra bulge. But do watch for that, particularly if you go over a bump and the bike 'thuds' more than normal.

There is also the ride-through-the-puddle test. Go through a puddle and onto a dry surface, e.g. a pavement or a hallway. If you look at how much water has been left behind you can get a comparative idea of how much of your tyre is in contact with the road. If you know what you expect and if the trail is thicker than that, e.g. with a lot more than the centre ridge making contact, then you may want to get the track pump out again.

Returning to the weight-on-the-wheel and how much the tyres splay idea, you can also roll your bike slowly over a kerb and see how much it deforms. At speed it will do so more than under the static situation, so try it slowly and there should be no danger to your rims and 'snake-biting' your tyres.

As for squeezing the tyre after inflating it as best as I can with a mini-pump, when I get to the track pump with gauge I am always surprised at how many tens of P.S.I. I was off the mark. Squeezing the tyre is a waste of time.

If you had car-type valves (which you don't) then you could get those valve caps that some car-part shops sell. These go red when you lose 5-10 P.S.I. They are good but not available in Presta to my knowledge.

Personally I find the best gauge to be how the bike feels and how fast it goes. On some parts of my commute I like to go quicker than the 20 m.p.h. speed limit (as cars cannot over take me then), however, there are times when I am not able to hit my expected speeds, as measured on the bike speedometer. With a bit of extra air in the tyres I can usually get back to where I expect to be.