Ok, so first let's see how a module would make this really simple.

perl -we 'use Date::Manip; 
$input = "200604131145"; 
$output = UnixDate(DateCalc(ParseDate($input), "15 minutes"), "%Q%H%M"
+); 
warn $output;'
[download]

Now if you are not allowed to use modules, you may still be able to copy the source of the Date::Manip module (surrounded by braces) to your perl script, or even copy only the relevant parts (I did that once on an online competition with a C library).