Well, mine only meets one of those requirements, it was ~£40, the QStarz Q1000p. However, I would say don't get caught up on it having to have aa/aaa (or any other easy to get hold of) battery type. Many devices nowadays will charge from USB. You can get solar, wind-up or battery powered mobile-saving devices to charge USB, and a GPS logger is going to be low powered. If you see a model you like, but it doesn't have the right battery, consider alternative charging methods before dismissing it.
Relatively cheap. It is ~3cm by 2cm by 5cm from memory.
Does not use aa/aaa, it has a proprietary lithium battery. However, it uses a 'standard' miniusb connector for both charging and data download. This means that you could get a wind-up, or mobile saver device to recharge it if you are worried about batteries. (I suspect that this could be done with most GPS data loggers, so unless you are really tight on space/weight, I wouldn't let the battery type hang you up too much)
Batteries last between 1 to 4 days, full usage. It can do logging at 5Hz (5 times per second), or up to never. It can log based on position, speed, time, and records HDOP,PDOP, NSAT etc. IF YOU WANT IT TO. If you do not want these, you turn them off, and the 4Mb of data storage will go further. I record HDOP and position only I think. This will last a significant time. I usually set it to every 5m I think, and use a computer to filter to HDOP <=2
It has no screen.
I have in the past recorded trans-atlantic plane flights, after the initial lock (which took ~5 hours after being shipped from HK), it usually locks within 20 seconds in a car (often a lot lot faster), and will sustain a lock better than some othe GPS devices I have.
To connect to it, you use USB or bluetooth. The bluetooth is good, when I have been on holiday, I set my laptop up to scan the bluetooth channels, when the GPS datalogger comes into range, the laptop automatically logs into it, downloads the RAW data, performs any UTC/GMT/daylight correction and splits the tracks into days. It also wipes the memory and resets the capture type, so I can just walk away and continue with the device (unless it needs charging).