I modified the video to 4 gray color level still with full resolution though (320x224) and lossless compression.
I tweaked a bit my compression and now i obtain this :
Original tiles size : 13118672
Packed tiles size : 5532992
RAW : 18946 tiles
packed RLE : 185222 tiles
packed RLE Rot : 212647 tiles
packed Plain + Pix : 170209 tiles
copy (flipped or not) : 232893 where 72150 tiles are used as reference.
Packed tilemap data size : 708437
Total data size : 6241429 bytes
still a lot more than the 3.5 MB max i want
If we take the packed tiles size, we can see i get a 42% compression ratio... not really good :-/