You may or may not be interested in Test::Without::Module, or the younger and more maintained implementations whose names escape me.

If you don't want to (or as in your case, can't) specify a version in your prerequisite, you can always use 0 or undef in place of the version number.

If you doubt my recommendation, I recommend to just use it and watch how the CPAN testers behave. There is no fee involved, and they won't send you angry mails about breaking your prerequisites either.