Generate Dennis Numbers

CJam, 45 bytes

0{{)_s:C,2m*{~Ce\is_W%=},,2/:O!CCW%=|}g}ri*SO

Try it online!

How it works

0          e# Push 0 (candidate).
{          e# Loop:
  {        e#   Loop:
    )_     e#     Increment the candidate and push a copy.
    s:C    e#     Cast to string and save in C.
    ,      e#     Get the length of C, i.e., the number of digits.
    2m*    e#     Push all pairs [i j] where 0 ≤ i,j < length(C).
    {      e#     Filter:
      ~    e#       Unwrap, pushing i and j on the stack.
      Ce\  e#       Swap the elements of C at those indices.
      is   e#       Cast to int, then to string, removing leading zeroes.
      _W%= e#       Copy, reverse and compare.
    },     e#     Keep the pairs for which = returned 1, i.e., palindromes.
    ,2/    e#     Count them and divide the count by 2 ([i j] ~ [j i]).
    :O     e#     Save the result (the order) in O.
    !      e#     Negate logically, so 0 -> 1.
    CCW%=  e#     Compare C with C reversed.
    |      e#     Compute the bitwise NOT of both Booleans.
           e#     This gives 0 iff O is 0 or C is a palindrome.
  }g       e#   Repeat the loop while the result is non-zero.
}ri*       e# Repeat the loop n times, where n is an integer read from STDIN.
           e# This leaves the last candidate (the n-th Dennis number) on the stack.
SO         e# Push a space and the order.

Pyth, 44 bytes

L/lf_ITs.e.e`sXXNkZYbN=N`b2,Je.f&!_I`ZyZQ0yJ

Try it online: Demonstration or Test Suite

A stupid little bug (?) in Pyth ruined a 41 byte solution.

Explanation:

L/lf_ITs.e.e`sXXNkZYbN=N`b2
L                             define a function y(b), which returns:
                      =N`b       assign the string representation of b to N
        .e             N         map each (k=Index, b=Value) of N to:
          .e         N             map each (Y=Index, Z=Value) of N to:
              XXNkZbN                switch the kth and Yth value in N
            `s                       get rid of leading zeros
       s                         combine these lists
   f_IT                          filter for palindromes
  l                              length
 /                        2      and divide by 2

,Je.f&!_I`ZyZQ0yJ
   .f        Q0     find the first input() numbers Z >= 0, which satisfy
      !_I`Z            Z is not a palindrom
     &                 and 
           yZ          y(Z) != 0
  e                 get the last number
 J                  and store in J
,J             yJ   print the pair [J, y(J)]

Haskell, 174 bytes

import Data.List
p x=x==reverse x
x!y=sum[1|(a,b)<-zip x y,a/=b]==2
o n|x<-show n=sum[1|v<-nub$permutations x,x!v,p$snd$span(<'1')v,not$p x]
f=([(x,o x)|x<-[-10..],o x>0]!!)

p checks whether a list is a palindrome.

x!y is True iff the lists x and y (which should have the same length) differ in exactly two places. Specifically, if x is a permutation of y, x!y determines whether it is a "swap".

o n finds the Dennis-order of n. It filters for swaps among the permutations of x = show n, and then counts how many of those swaps are palindromes. The list comprehension that performs this count has an extra guard not (p x), which means it will return 0 if n was a palindrome to begin with.

The snd (span (<'1') v) bit is just dropWhile but one byte shorter; it turns "01221" into "1221".

f indexes from a list of (i, o i) where o i > 0 (i.e. i is a Dennis number.) There would normally be an off-by-one error here, as (!!) counts from 0 but the problem counts from 1. I managed to remedy this by starting the search from -10 (which turned out to be considered a Dennis number by my program!) thereby pushing all the numbers into the right spots.

f 774 is (12012,3).