CJam, 119 91 bytes

q~:M;),>:R;(:L{{R{ML)d/-Y#)mr}$L/L<2{{M1$:+-+}%z}*:U:+__O|=R*-}gU{:s_:,:e>f{Se[}}%zSf*N*}M? 

This is a provably correct, non-deterministic approach.

On my desktop, the second test case generally finishes in less than 10 minutes.

The first case finishes instantly. Try it online in the CJam interpreter.

Sample run

$ cjam grid.cjam <<< '8 1 300 500' 77 66 37 47 56 46 86 85 63 102 70 72 49 54 81 9 62 69 58 57 71 17 48 118 64 65 67 87 53 44 80 40 73 60 55 89 51 76 84 12 68 59 28 78 74 38 50 105 61 75 52 43 125 83 42 19 32 4 133 27 21 142 29 112 

Idea

Without time limits, we could just randomly generate squares until finding a valid square. This approach builds on that idea, adding two optimizations:

• Instead of pseudo-randomly generating square of side length N, we generate squares of side length N-1, add one column to form a N × (N-1) rectangle whose rows have sum S, then one row to form a square of side length N whose columns have sum S.

  Since the sum of the elements of all columns will be NS and the sum of the elements of the first N-1 rows is (N-1)S, the last row will also have sum S.

  However, this process may generate an invalid matrix, since there's no guarantee that all elements of the last row and column will be unique or fall in the range [A ... B].

• Picking a square of unique integers in [A ... B] and side length N-1 uniformly at random would take way too long. We somehow have to prioritize squares that have a higher chance of resulting in a valid square of side length N after applying the process detailed in the previous bullet point.

  Given that each row and column has to have a sum of S, its elements have an average of S/N. Thus, picking more elements close to that average should increase our chances.

  For each I in [A ... B], we pseudo-randomly pick a float between 0 and (I - S/N)² + 1 and sort the elements of [A ... B] by the picked floats. We keep the first N² numbers and place them in reading order in a square.

  Assuming a perfectly uniform distribution of all real numbers between 0 and (I - S/N)² + 1 in each step, all squares have a non-zero probability of being picked, meaning that the process will finish eventually.

Code

q~ e# Read all input from STDIN and evaluate it. :M; e# Save "S" in M and discard it from the stack. ),>:R; e# Transform "A B" into [A ... B], save in R and discard. (:L e# Save "N - 1" in L and keep it on the stack. { e# If L is non-zero: { e# Do: R{ e# For each I in R: ML)d/ e# Compute M/Double(L+1). -Y# e# Subtract the result from I and square the difference. )mr e# Add 1 and pick a non-negative Double below the result. }$ e# Sort the values of I according to the picks. L/ e# Split the shuffled R into chunks of length L. L< e# Keep only the first L chunks. 2{ e# Do twice: { e# For each row of the L x L array. M1$ e# Push M and a copy of the row. :+- e# Add the integers of the row and subtract their sum from M. + e# Append the difference to the row. }% e# z e# Transpose rows and columns. }* e# :U:+ e# Save the result in U and concatenate its rows. __O| e# Push two copies. Deduplicate the second copy. =R* e# Push R if all elements are unique, an empty array otherwise. - e# Remove the result's elements from U's elements. }g e# If the resulting array is non-empty, repeat the loop. U{ e# For each row in U: :s e# Convert its integers into strings. _:, e# Copy and replace each string with its length. :e> e# Compute the maximum length. f{ e# For each integer, push the maximum length; then Se[ e# Left-pad the integer with spaces to that length. } e# }% e# z e# Transpose rows with columns. Sf*N* e# Join columns by spaces, rows by linefeeds. }M? e# Else, push M.