1. use an interrupt on one pin to increment a counter
2. set the counter to 0 and startTime to millis()
3. monitor millis() in the loop for millis()- startTime > 250
4. grab the accumulated value of the counter and do something with it.
Yes, yes, yes, and yes.
In your previous post, you are correct, while "count something" is running, nothing else is running. At the lowest level, the processor is only executing a single instruction at any given time. As we have only a single processor, it is physically impossible to run more than one instruction at a time. Any appearance to the contrary is just an illusion, caused by the speed of the processor and careful control of program flow and execution. Now if some interrupt is enabled, of course it is entirely possible that "count something" is interrupted, control transferred to the interrupt service routine, and then "count something" resumes when the ISR completes.
If you understand the "BlinkWithoutDelay" sketch, you will be well on your way. To test your comprehension, try writing a sketch that blinks two LEDs independently at different rates. Say, blink one once per second and another twice per second.
Note that there is some protocol to follow when sharing a variable between an interrupt service routine and the main program (loop). Because we only have an 8-bit processor, depending on the data type of the counter, it may take the main program more than one instruction to fetch it, zero it, etc. If the main program is in the middle of doing this when the interrupt fires, we can get invalid results. To avoid this, use the volatile qualifier when declaring the variable, and inhibit interrupts any time the variable is being accessed, updated, etc. by the main program. See the doc on the cli() and sei() functions.